Full search motion estimation in real-time video coding requires large amount of computations. Reducing computational cost for full search motion estimation is critical research issue for enabling fast real-time video coding such as MPEG-4 advanced video coding. In this paper, we propose a novel fast full search block matching algorithmwhich significantly reduces unnecessary computations without affecting motion prediction quality. The proposed algorithm identifies computational matching order from initial calculation of matching differences. According to the computational order identified, matching errors are calculated based on partial distortion elimination method. The proposed algorithm could reduce about 45% of computational cost for calculating block matching errors compared with the conventional algorithm without degrading any motion prediction quality. The proposed algorithm will be particularly useful for realizing fast real-time video coding applications, such as MPEG-4 advanced video coding, that require large amount of computations.