In the advanced H.264 video coding, the computation complexity is much higher than the previous video coding standards due to the variable block size and multi-reference frame features which are used in the motion compensation process. This paper proposes a hierarchical H.264 fast motion estimation algorithm to decrease the coding complexity in both spatial and temporal domains for encoding high-definition videos. In the spatial domain, we utilize the fast search method with a hierarchical-subsampling structure to decrease the memory access bandwidth of search points. In the temporal domain, we employ the linear motion model to further reduce the search ranges of multiple reference frames. This search algorithm is particularly suitable for being implemented in the parallel-processing architecture with the limited hardware resources. Simulation results show that the proposed algorithm can reduce up to 98.2% computation complexity of Full Search in JM with less than 0.1 dB video quality degradation.