The stability of the flow of a viscoelastic fluid over a deformable elastic solid medium is reviewed focusing on the role played by the fluid elasticity on the earlier known instability modes for the Newtonian fluids. In particular, two classes of modes are emphasized: the viscous mode for the creeping flow, and the wall mode for high Reynolds number flow. The flow geometry is restricted to plane Couette flow of fluid supported on elastic substrate of finite thickness. The viscoelastic fluid is described using the Oldroyd-B model and the dynamics of the deformable solid continuum is described by either Hookean or neo-Hookean elastic model. In the limit of $Re \to 0$, the introduction of fluid elasticity delays the onset of instability and for sufficiently viscoelastic fluid with dilute polymer concentration, the instability is suppressed rendering the flow stable. For concentrated solution and polymer melt, the instability persists, but with higher value of critical shear rate than for the Newtonian fluid, indicating stabilizing role of fluid elasticity in creeping flow regime. However, for high Reynolds number flow of dilute polymer solution, the polymer addition plays a destabilizing role for wall modes, indicated by reduction in critical Reynolds number by an order of magnitude.