This paper presents a novel method for estimating the velocity of a mobile station (MS) in a typical macro-cell. The proposed estimator uses the auto-correlation function of the instantaneous frequency (IF) of the received signal at the MS antenna. The performance of the proposed estimator in the presence of shadowing, additive noise, and non-isotropic scattering is studied analytically. It is proved that, unlike existing velocity estimators, the IF-based estimator is robust to shadowing