A new method of motion estimation based on the search of the local extremum was proposed to reduce the time of motion estimation in the video encoding. Firstly, divided the search area into several parts according to the size of the search blocks; Secondly, started to find the local extremum of the search part in spiral way and compared it with the extremum ahead. In this step, early termination strategy and the algorithm of marking and skipping were proposed so as to further speed up the search. In the last, took the minimum value of the search parts as the global minimum and searched that part with the diamond pattern in the step of 1, which could get the perfect location. Test results show that compared with the UMH, the new method can improve the encoding speed but the PSNR increases less than 0.03 kb/s and the bitstream rate decreases less than 0.005 dB. What’s more, this method can reduce the encoding time by 10% compared with the UMH when encoding the video which has very high motion complexity.