In this paper we solve the time-dependent shear flow of an Oldroyd-B fluid with slip along the fixed wall. We use a non-linear slip model relating the shear stress to the velocity at the wall and exhibiting a maximum and a minimum. We assume that the material parameters in the slip equation are such that multiple steady-state solutions do not exist. The stability of the steady-state solutions is investigated by means of a one-dimensional linear stability analysis and by numerical calculations. The instability regimes are always within or coincide with the negative-slope regime of the slip equation. As expected, the numerical results show that the instability regimes are much broader than those predicted by the linear stability analysis. Under our assumptions for the slip equation, the Newtonian solutions are stable everywhere. The interval of instability grows as one moves from the Newtonian to the upper-convected Maxwell model. Perturbing an unstable steady-state solution leads to periodic solutions. The amplitude and the period of the oscillations increase with elasticity.