In video coding, research is focused on the development of fast motion estimation (ME) algorithms while keeping the coding distortion as small as possible. It has been observed that the real world video sequences exhibit a wide range of motion content, from uniform to random, therefore if the motion characteristics of video sequences are taken into account before hand, it is possible to develop a robust motion estimation algorithm that is suitable for all kinds of video sequences. This is the basis of the proposed algorithm. The proposed algorithm involves a multistage approach that includes motion vector prediction and motion classification using the characteristics of video sequences. In the first step, spatio-temporal correlation has been used for initial search centre prediction. This strategy decreases the effect of unimodal error surface assumption and it also moves the search closer to the global minimum hence increasing the computation speed. Secondly, the homogeneity analysis helps to identify smooth and random motion. Thirdly, global minimum prediction based on unimodal error surface assumption helps to identify the proximity of global minimum. Fourthly, adaptive search pattern selection takes into account various types of motion content by dynamically switching between stationary, center biased and, uniform search patterns. Finally, the early termination of the search process is adaptive and is based on the homogeneity between the neighboring blocks. Extensive simulation results for several video sequences affirm the effectiveness of the proposed algorithm. The self-tuning property enables the algorithm to perform well for several types of benchmark sequences, yielding better video quality and less complexity as compared to other ME algorithms. Implementation of proposed algorithm in JM12.2 of H.264/AVC shows reduction in computational complexity measured in terms of encoding time while maintaining almost same bit rate and PSNR as compared to Full Search algorithm. © 2011 Elsevier B.V. All rights reserved.