Motion estimation (ME) is the exploitation of similarities between adjacent frames in a video sequences, and is an essential part of the H.264 and other video compression standards. However, it introduces an increase of computation complexity resulting in longer execution time. In this paper, the search range for block-matching ME is made adaptive, based on the motion vectors present in preceding frames. The proposed algorithm determines the amount of motion in past frames and classifies the video sequence as having low, medium or high motion. This classification and the direction of the motion vectors, are used to dynamically adjust the search window size and general orientation. Simulation results show that execution time could be reduced by 42 - 60 with a small degradation in PSNR value, to that of non-adaptive ME. © 2006 IEEE.