Rate-distortion optimization can significantly improve encoder performance in MPEG-like video coding applications. Nevertheless, mode selection and motion estimation (ME) in a rate-distortion optimized setting can entail a prohibitive computational cost. In this paper, we propose a macroblock mode selection algorithm by employing computationally-efficient, yet highly-effective rate-distortion models. We also consider joint optimization of the ME with the mode selection. With our extensive analysis on various video sequences, we show that the proposed algorithm provides significant improvements with negligible increase in overall computational load. With the proposed method, we achieve 3.13, 1.78, and 1.64 dB peak signal-to-noise ratio gains over TM5 on the average, at the bit rates 2, 4, and 6 Mb/s, respectively, with CCIR-601 video. (More information about the DSP/VLSI implementation of the proposed algorithm may be found online at: http://www.ece.gatech.edu/research/labs/MCCL).