In most block-based video coding systems, some of the fast block matching algorithms use the origin as the initial search center. But the tracking result of these algorithms is not well enough. To improve the accuracy of the fast block matching algorithms, a new adaptive return prediction (ARP) search algorithm is proposed in this paper. The proposed algorithm exploits the temporal correlation and the characteristic of returning phenomenon to obtain one or two predictive motion vectors, and one of the predictive motion vectors are chosen as the initial search center. This predicted search center is found closer to the global minimum, thus the center-biased algorithm can find the motion vector more efficiently. Simulation results show that the proposed algorithm enhances the accuracy of BMA as well as reduces their computational requirement.