Most of the hierarchical block matching algorithms reduce computation by matching only some of the locations inside the search area. In this paper, we propose a novel hierarchical partial distortion search (HPDS) algorithm which reduces the computation of each distortion measure instead of the number of checking points by using partial distortion measure. Experimental results show that the proposed algorithm provides 6 times speed up as compared with full search while maintains the MSE performance very close to full search. Moreover, it can also achieve 20 times speed up when the MSE performance is kept close to the well-known three-step search. With appropriate parameter selections, the proposed algorithm can fit HDTV and MPEG-2 applications where high motion estimation accuracy is required, or real-time video conferencing applications where encoding speed is critical.