The MPEG-2 has become popular as the digital broadcasting video standard. Meanwhile, MPEG-4 simple profile (SP) is rapidly growing in its market of low bit rate multimedia applications, such as internet video streaming service, mobile PC, and mobile phone. Thus, it is often necessary to convert a high bit rate MPEG-2 bitstream into a low bit rate MPEG-4 SP bitstream. But MPEG-2 and MPEG-4 SP are different in their scan format, picture type, and group of picture (GOP) structure as well as their image size and bit rate. In this paper, we propose an efficient motion vector (MV) re-estimation method for transcoding MPEG-2 to MPEG-4 SP. In the proposed method, we first choose only top field MVs, and replace their references with top field ones for scan format conversion. Then, by selecting MV candidates and modifying them so that they may comply with the output picture type and GOP structure, we prepare a set of candidate MVs and select their median vector as a macroblock MV in MPEG-4. Meanwhile, to utilize the advanced prediction mode of MPEG-4, we also perform block-based refinement using the selected macroblock MV. The experimental results show that the proposed motion re-estimation method reduces the encoder complexity to about 50% with a minor PSNR degradation compared with motion estimation based on full search.