Though H.264 is highly efficient compared to MPEG-2, the wide and deep penetration of MPEG-2 creates a need for co-existence of these technologies and hence creates a need for transcoding. In this paper, we introduce and evaluate a novel macroblock partition mode decision algorithm for inter-frame prediction to be used as part of a high-efficient 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 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 obtaining the H.264 coding decision modes. Our results show that the proposed algorithm is able to maintain a good picture quality while considerably reducing the number of operations to be performed. ©2006 IEEE.