For improvement of coding efficiency, the H.264 video coding standard uses new coding tools, such as variable block size, quarter-pixel-accuracy motion estimation, multiple reference frames, intra prediction, loop filter, etc. Using these coding tools, H.264 achieves significant improvement in coding efficiency compared with existing standards. However, encoder complexity increases tremendously. Among the tools, the macroblock mode selection and the motion estimation contribute most to total encoder complexity. This paper focuses on complexity reduction in macroblock mode selection. Of all macroblock modes which can be selected, inter8?8 and intra4?4 have the highest complexity. We propose two methods for complexity reduction of inter8?8 and intra4?4 by using the costs of the other macroblock modes. Simulation results show that the proposed methods save up to 57.7% of total encoding time compared with the H.264 reference implementation, whereas the average PSNR only decreases less than 0.05dB.