The best performance in compression efficiency is provided by MPEG-4 AVC/H.264 but at the cost of high computational complexity to select the best mode during the mode decision process. To reduce this complexity, we propose a fast mode decision algorithm that exploits the spatiotemporal correlation of the macroblock (MB) modes and the rate-distortion (RD) costs from the previous and current frames. The proposed method determines the candidate modes for the current MB based on the modes of the four spatially neighboring and temporally collocated MBs. It also incorporates the RD costs of the four reference MBs and the current MB. The experimental results show that the AVC/H.264 encoder using our proposed method achieves about 73% speedup (up to 86.5%) compared to the AVC/H.264 JM 11.0 encoder while preserving a 0.25% increment in total encoding bits with a loss of only 0.09 dB in peak SNR.