The latest emerging video compression standard, H.264/AVC, achieves better compression performance than previous standards. Variable block size based motion estimation (ME) with optimized mode decision (MD) is one of the most important improvements leading to high quality and low bitrate encoding results. However, such improvement is at the cost of remarkably complex calculation, which is a major bottleneck for some applications, especially in wireless communications. A new MD algorithm is presented in this paper. Taking into account the correlation between macroblocks, the computational complexity is reduced significantly by effectively skipping some unnecessary modes. Experimental results show that the encoding time can be reduced up to 55.26% with negligible loss of encoding efficiency.