We propose a velocity estimation scheme for mobile stations (MSs) in cellular communication systems that uses the azimuth spread (AS), delay spread (DS), and shadow fading of MSs. Due to the fact that the AS, DS, and shadow fading are correlated in the spatial domain, the variation of the AS, DS, and shadow fading of an MS is related to its velocity. And, we also consider the variation of velocity which was not considered in previous velocity estimation studies. Through analysis and numerical results, we show that we can estimate the velocity of an MS with lower estimation error compared to previous estimation schemes, despite of measurement error.