We introduce a new technique with high time resolution to measure surface diffusion by monitoring the time dependence of the STM tunneling current fluctuations. Diffusion parameters may be extracted from the decay of the tunneling current fluctuation autocorrelation function, c(t) = \langle[delta] i(0)[delta] i(t)\rangle , or from its Fourier transform, the power spectrum, W(f). Results were obtained for W(f) of oxygen adsorbed on stepped Si(111). Spectra for clean Si(111) show no temperature dependence while that for oxygen-covered Si(111) have signals which are two orders of magnitude greater and exhibit a strong temperature dependence: the spectra broadens with increasing temperature. The data fit the expected theoretical form well and by considering the low frequency regime, W(f) ~ -ln(f)/D, f → 0, the diffusion barrier for O/Si(111) was extracted, giving Ed = 0.92 ± 0.15 eV;The technique is tested if it can distinguish adsorbate diffusion from other surface processes which may interfere with the measurement. We have investigated how certain factors influence the shape of the correlation function or the power spectrum through a combination of experiments and Monte Carlo simulations. These factors include simultaneous diffusion on the substrate and on the tip, and the effect of inhomogeneous surface potentials caused by the electric field or impurities. Simultaneous diffusion on the substrate and on the tip produces a two-segment correlation function which is easily distinguished from that of a single diffusion process. Surface diffusion in inhomogeneous surface potentials (which can cause atoms to diffuse toward or away from the tip) result in correlation functions and power spectra that deviate from the theoretical forms as well. The technique is very highly local, can be used in a wide range of temperatures, and is able to measure a rather wide range of diffusion coefficients: ~10-15-10-8 cm2/sec.