In this paper, we proposed an early zero-block detection algorithm for motion search in H.264/AVC to reduce the computation using a nearly sufficient condition for zero-block detection of 4×4 DCT coefficients after quantization. The early zero-block detection approach was applied to the hybrid UMHexagonS algorithm that has been adopted in JM reference software. The experimental results indicated that a significant improvement in computation reduction was achieved. The PSNR loss as well as hit-rate increment, however, is not negligible, especially for high QP or low bit-rate coding. In addition, the early detection algorithm is modified in the UMHexagonS algorithm to improve the coding performance. Experimental results show that great reduction in computation can be achieved while still maintaining high coding efficiency.