On the Sun, the rotation periods of individual sunspots not only trace the latitude dependence of the surface rotation rate, but also provide clues as to the amount of subsurface fluid shear. In this paper we present the first measurements of stellar differential rotation made by tracking the rotation of individual starspots with sizes comparable to the largest sunspots. To achieve this we re-analyse four sequences of densely-sampled, high signal-to-noise echelle spectra of AB Doradus spanning several stellar rotations in 1996 December. Using spectral subtraction, least-squares deconvolution and matched-filter analysis, we demonstrate that it is possible to measure directly the velocity amplitudes and rotation periods of large numbers of individual starspots at low to intermediate latitude. We derive values for the equatorial rotation rate and the magnitude of the surface differential rotation, both of which are in excellent agreement with those obtained by Donati & Collier Cameron (1997) from cross-correlation of Doppler images derived a year earlier in 1995 December, and with a re-analysis of the 1996 data by the method of Donati et al (2000). The differences between the rotation rates of individual spots and the fitted differential rotation law are substantially greater than the observational errors. The smaller spots show a greater scatter about the mean relation than the larger ones, which suggests that buffeting by turbulent supergranular flows could be responsible.