In this paper, we propose a dynamic bit-rate reduction scheme for transcoding an MPEG-1 bitstream into an MPEG-4 simple profile bitstream with a typical bit-rate of 384 kbps. For dynamic bit-rate reduction, a significant reduction in the bit-rate is achieved by combining the processes of requantization and frame-skipping. Conventional requantization methods for a homogeneous transcoder cannot be used directly for a heterogeneous transcoder due to the mismatch in the quantization parameters between the MPEG-1 and MPEG-4 syntax and the difference in the compression efficiency between MPEG-1 and MPEG-4. Accordingly, to solve these problems, a new requantization method is proposed for an MPEG-1 to MPEG-4 transcoder consisting of R-Q (rate-quantization) modeling with a simple feedback and an adjustment of the quantization parameters to compensate for the different coding efficiency between MPEG-1 and MPEG-4. For bit-rate reduction by frame-skipping, an efficient method is proposed for estimating the relevant motion vectors from the skipped frames. The conventional FDVS (forward dominant vector selection) method is improved to reflect the effect of the macroblock types in the skipped frames. Simulation results demonstrated that the proposed method combining requantization and frame-skipping can generate a transcoded MPEG-4 bitstream, that is much closer to the desired low bit-rate than the conventional method along with a superior objective quality.