In this paper, a modified bit-rate estimation method is proposed to reduce the computation for 4×4 intra mode decision of H.264/AVC video encoder. The number of coded bits is modeled by a linear combination of existing coding parameters, which are highly related to the entropy coding of H.264/AVC. Furthermore, to improve the accuracy of the estimation, the proposed scheme is made adaptive to the information obtained from previously coded blocks. Comparing to the original rate distortion optimized (RDO) encoding process, which needs to calculate the actual encoded bits of H.264/AVC for each coding mode, the proposed adaptive rate estimation can save about 28% and 21% of the total encoding time for QCIF and VGA sequences, respectively. For the coding performance, the proposed method achieves nearly no loss in visual quality with only slight bit-rate increases.