In the current applications such as video conferencing, the video codec speed is the key factor to maintain the real-time performance in the whole system. In order to minimize the computations and improve the performance of video coding, an adaptive zero block detection algorithm combined with multi-resolution motion estimation is proposed in this paper. The multi-resolution technique uses down-sampling method on the whole image, which can dramatically reduce the computations in searching for the best candidate block during the motion search period. At the same time, adaptive zero block detection criteria can make the motion search procedure even faster and improve the coding efficiency without any influence on the image quality. Furthermore, the run-time of DCT(discrete cosine transform) and quantization has been singificantly reduced afterwards. Simulation results show that with H.263 codec, the proposed algorithm can obtain 40% savings in computations at most without any losses in the subjective and objective quality of decoded images.