The H.264 standard achieves much higher coding efficiency than the MPEG-2 standard, due to its improved inter and intra prediction modes which come with a cost of higher computation complexity. Transcoding MPEG-2 video to H.264 is important to enable gradual migration to H.264. However, given the significant differences between the MPEG-2 and the H.264 coding algorithms, transcoding is much more complex and new approaches to transcoding are necessary. In this paper, we introduce and evaluate a low complexity macroblock partition mode decision algorithm, to be used as part of a high-efficient inter-frame prediction in MPEG-2 to H.264 transcoder. The proposed tools are used to compute an optimal MB coding mode decision with significantly reduced computational complexity. Specifically, we achieve the computational savings by using the following MB information coming from MPEG-2: the MB coding modes, the coded block pattern (CBPC) in MPEG-2, and the mean and variance of the 16 4∈×∈4 sub blocks of the MPEG-2 residual MBs. We use data mining algorithms to develop a decision tree for H.264 coding mode decisions. The decision trees are built using RD optimized mode decisions and result in highly efficient mode decisions, with significantly reduced computational complexity. The proposed transcoder is 35% faster than the RD optimized H.264 reference transcoder without a significant PSNR degradation (0.05 dB on average). The proposed transcoder performs over 0.4 dB better on average than the SAE cost based H.264 transcoding. © 2007 Springer Science+Business Media, LLC.