Compared to conventional video standards, the main features of H.264 standard are its high coding efficiency and its network friendliness. In spite of these outstanding merits, it is not easy to implement H.264 codec as a real-time system, due to its requirements of large memory bandwidth and intensive computation. Although the variable-block-size motion compensation using multiple reference frames is one of the key coding tools to bring about its main performance gain, its optimal use demands substantial computation for the rate-distortion calculation of all possible combinations of coding modes and estimation of the best motion vector. Many existing fast motion estimation algorithms are not suitable for H.264, which employs variable motion block sizes. We propose an adaptive motion search scheme utilizing the hierarchical block structure based on the deviation of subblock motion vectors. The proposed fast scheme adjusts the search center and search pattern according to the subblock motion-vector distribution.