In this paper, we introduce and evaluate a low complexity macroblock partition mode decision algorithm for interframe 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 4x4 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. The proposed transcoder is 35% faster than the RD optimized H.264 reference transcoder without a significant PSNR degradation. The proposed transcoder performs over 3 dB better than the SAE cost based H.264 transcoding. © 2006 IEEE.