The H.264 standard applies several powerful coding methods to obtain high compression efficiency. However, it requires a lot of computation especially in variable block-size motion estimation. To reduce the motion estimation redundancy more effectively, an adaptive early termination algorithm is proposed in this paper. The proposed algorithm dynamically changes the thresholds for different coding modes according to video content. With the proposed method, many zero motion blocks can be predicted, the corresponding motion estimation can stop early, and the remaining computation can be omitted. Simulation results show that the proposed method can averagely reduce the entire coding time up to 14.38% and the motion estimation time up to 21.82% at the price of negligible coding loss.