Since variable block-size motion compensation (MC) and rate-distortion optimization (RDO) techniques are adopted in H.264/MPEG-4 AVC, modes and motion vectors (MVs) in input stream can no longer be reused equivalently efficient over a wide range of bit rate in transcoded streams. This paper proposes a new RDO model to maintain good coding efficiency and greatly reduce computation of the H.264/MPEG-4 AVC transcoding, in which the distortion caused by motion and mode changes is not calculated directly from the sum of absolute difference (SAD) or the sum of square difference (SSD) between source signals and interpolated prediction signals. Instead, distortion is directly estimated from MV variation and the power spectrum (PS) of the prediction signal generated from input stream. The proposed RDO model can be applied to both the pixel-domain transcoding and the transform-domain transcoding even when coded signals are not reconstructed at all. Furthermore, the techniques as to derive the Lagrangian multiplier in the proposed model are developed in respective pixel- and transform-domains. Additionally, we propose an H.264/MPEG-4 transcoding scheme that demonstrates the advantage of the proposed RDO model in terms of peak signal-to-noise ratio and transcoding speed, in which P-pictures are transcoded in the pixel domain for achieving reconstructed high quality and B-pictures are transcoded in the transform domain for high-transcoding speed.