The stability of the large Reynolds number flow of a Newtonian fluid over a much more viscous viscoelastic fluid is studied via a linear analysis. The two fluids are confined within a channel and the flow is driven by the motion of the plate bounding the Newtonian fluid. Matched asymptotic expansions are used to derive the dispersion relation, and the flow is found to be always unstable to an interfacial mode due to the discontinuity in the fluid viscosities. It is shown that even a small amount of elasticity of the viscoelastic fluid can change the stability characteristics considerably.