On the basis of the UMHexagonS algorithm used in the Joint Model(JM) for H.264, a new fast algorithm on integer pixel motion estimation was proposed to improve the video encoding characteristics. A new order of checking predicted Motion Vector(MV) was proposed in the predicting starting search point to promote the accuracy of starting search point. Then, a self-adaptive global search method was proposed for the global search, by which the unsymmetrical-cross search and uneven multi-hexagon-grid search could be skipped based on the relationship between two predicted MVs with highest accuracy, and the feasibility and accuracy of this judging method was verified through tests on a number of different sequences. Meanwhile, an improved 5×5 search method was presented according to the distribution of best MV relative to the starting search point and a new early termination technique for sub-macroblock was added to further reduce the cost of motion estimation without additional computation. According to the experiment results, the proposed algorithm reduces the total number of search points by 83.80% and the Peak Signal to Noise Ratio(PSNR) about 0.021 dB on average and increases an average increment of 0.46% on equivalent bitrates as compared with that of original UMHexagonS algorithm. With a negligible performance degradation, the proposed algorithm reduces the computation of motion estimation effectively and offers a well-distributed effect on sequences with different motion intensities.