The intensive search of optimal matching block greatly increases the complexity of motion estimation that constitutes the most time-consuming part of H.264/AVC. This thesis presents a novel fast hierarchical motion search (FHMS) strategy along with a heuristic early termination technique. The proposed FHMS paradigm is based on the observation that most search operations can be avoided by sub-sampling current macroblocks first to reduce the dimensions of both reference pictures and search range. The early termination establishes a statistical threshold that makes motion search for stationary or quasi-stationary areas to terminate earlier without sacrificing accuracy. Experimental results show the proposed FHMS is highly time-efficient in finding the motion vectors and at the same time maintaining satisfactory video quality.