Many modern video encoders use the Lagrangian rate-distortion optimization (RDO) algorithm for mode decisions during the compression procedure. For each encoding stage, this approach involves minimizing a cost, which is a function of rate, distortion and a multiplier called Lambda. This paper proposes to improve the RDO process by applying two modifications. The first modification is to increase the accuracy of rate estimation, which is achieved by computing a non-integer number of bits for arithmetic coding of the syntax elements. This leads to a more accurate cost computation and therefore a better mode decision. The second modification is to search and adjust the value of Lambda based on the characteristics of each coding stage. For the encoder used, this paper proposes to search multiple values of Lambda for the intra-4×4mode decision. Moreover, a simple shift in Lambda value is proposed for motion estimation. Each of these modifications offers a certain gain in RDO performance, and, when all are combined, an average bit-rate saving of up to 7.0% can be achieved for the H.264/AVC codec while the same concept is applicable to the H.265/HEVC codec as well. The extra added complexity is contained to a certain level, and is also adjustable according to the processing resources available.