An improved algorithm is proposed based on unsymmetrical cross multi-hexagon grid search(UMHexagonS), which is a fast motion estimation algorithm recommended by H.264. In the prediction link for initial search points, predictive vector sets are established, and the follow-up search strategy is determined according to the length of prediction vector sets. In the global search link, the correlation between prediction motion vectors is used to skip some search steps, and some templates are replaced. In addition, the block of zero coefficients is detected to terminate the motion estimation process in advance, according to characteristics of integer transform and quantization. Experimental results show that, when the quantization step size is 28, the proposed algorithm reduces the motion estimation time by 34.80% compared with the UMHexagonS algorithm, while maintaining the performance. Finally, the algorithm can adapt to video sequences with different motion intensity under different quantization steps, which is a fast motion estimation algorithm with fast speed and good performance suiting for H.264.