In low bit-rate video coding, all-zero block determination is a common technique to reduce the computational complexity of the encoder. We aim to improve the algorithm for the early detection of zero-blocks in H.264 video encoding. An improved algorithm for the early detection of all-zero blocks in H.264 video encoding is proposed in this paper. Based on the theoretical analyzes for the integer transform and quantization in H.264, a precise sufficient condition is proposed by modifying the calculation formula of discrete cosine transform in the motion estimation. The simulation results show that the proposed algorithm achieves approximately an 12%–39% computational saving without video-quality degradation, compared to the conventional method.