The latest H.264/AVC video coding standard aims at significantly improving compression performance compared to all existing video coding standards. In order to achieve this, variable block-size inter- and intra-coding, with block sizes as large as 16 × 16 and as small as 4 × 4 , is used to enable very precise depiction of motion and texture details. The Lagrangian rate-distortion optimization (RDO) can be employed to select the best coding mode. However, exhaustively searching through all coding modes is computationally expensive. This paper proposes a scalable fast RDO algorithm to effectively choose the best coding mode without exhaustively searching through all the coding modes. The statistical properties of MBs are analyzed to determine the order of coding modes in the mode decision priority queue such that the most probable mode will be checked first, followed by the second most probable mode, and so forth. The process will be terminated as soon as the computed rate-distortion (RD) cost is below a threshold which is content adaptive and is also dependent on the RD cost of the previous MBs. By adjusting the threshold we can choose a good tradeoff between timesaving and peak signal-to-noise (PSNR) ratio. Experimental results show that the proposed fast RDO algorithm can drastically reduce the encoding time up to 50% with negligible loss of coding efficiency.