Abstract: Fast mode decision is a key issue in real-time application of the H.264. In this paper, a new scheme of fast variable block size motion estimation with sub-pixel refinement is proposed. This algorithm uses the statistical information, which features the motion activities of the blocks in the previous frame, to predict the characteristics of the motion activities of the blocks in the current frame. Both distortion values and motion vectors of Macro Blocks(MB) in the previous frame are considered. With this prior knowledge, we can make decision on early rejection of sub-partition modes. Extensive experimental work has been done, results of which showed that the approach gives a speedup of 57% over that of thel algorithm in JM, with a negligible degradation in peak signal-to-noise ratio(PSNR) and bitrate.