In this paper a two-stage mode selection (TSMS) algorithm is presented to speed up the H.264/AVC video encoding process with rate distortion optimization (RDO). However, lots of additional computing power is required and this makes the realization of H.264/RDO in a resource-limited system very difficult. The proposed TSMS employs a two-stage decision process: the first stage is to predict some probable encoding modes according to the information when one encodes the preceding macroblocks and video frames. The second stage refines the decision with techniques based on Baye's probability rule and Back-Propagation neural network (BPN). According to the experiment results, over 50% of the computation time is reduced with very slight loss in peak signal-to-noise ratio (PSNR) and a slightly increment in bit rate when TSMS is applied. The TSMS is even faster than the encoding program with running RDO part. All programs are based on the H.264/AVC standard reference software (JM 9.2).