There is the spatial correlation of the video sequence between the motion vector of current blocks. In this paper, we propose the enhanced fast block matching algorithm using the spatial correlation of the video sequence and the center-biased property of motion vectors. The proposed algorithm determines an exact motion vector using the predicted motion vector from the adjacent macro blocks of the current frame and the Cross-Hexagonal search pattern. From the experimental results, we can see that our proposed algorithm outperforms both the prediction search algorithm (NNS) and the fast block matching algorithm (CHS) in terms of the search speed and the coded video’s quality. Using our algorithm, we can improve the search speed by up to 0.1～38%, and also diminish the PSNR (Peak Signal Noise Ratio) by at most 0.05~2.5 dB, thereby improving the video quality.