The stability of plane Couette flow of an upper-convected Maxwell (UCM) fluid of thickness R, viscosity eta and relaxation time tau(R) past a deformable wall (modeled here as a linear viscoelastic solid fixed to a rigid plate) of thickness HR, shear modulus G and viscosity eta, is determined using a temporal linear stability analysis in the creeping-flow regime where the inertia of the fluid and the wall is negligible. The effect of wall elasticity on the stable modes of Gorodtsov and Leonov [J. Appl. Math. Mech. 31 (1967) 310] for Couette flow of a UCM fluid past a rigid wall, and the effect of fluid elasticity on the unstable modes of Kumaran et al. [J. Phys. II (Fr.) 4 (1994) 893] for Couette flow of a Newtonian fluid past a deformable wall are analyzed. Results of our analysis show that there is only one unstable mode at finite values of the Weissenberg number, W = tau(R) V/ R (where V is the velocity of the top plate) and nondimensional wall elasticity, Gamma = Veta/(GR). In the rigid wall limit, Gamma much less than 1 and at finite W this mode becomes stable and reduces to the stable mode of Gorodtsov and Leonov. In the Newtonian fluid limit, W --> 0 and at finite Gamma this mode reduces to the unstable mode of Kumaran et al. The variation of the critical velocity, F, required for this instability as a function of W = tau(R)G/eta (a modified Weissenberg number) shows that the instability exists in a finite region in the Gamma(c) - W plane when Gamma(c) > Gamma(c),(Newt) and W < W-max, where Gamma(c,Newt) is the value of the critical velocity for a Newtonian fluid. The variation of F with W for various values of H are shown to collapse onto a single master curve when plotted as Gamma(c)H versus W/H, for H much greater than 1. The effect of wall viscosity is analyzed and is shown to have a stabilizing effect. (C) 2003 Elsevier B.V. All rights reserved.