Phosphorus (P) is an essential nutrient for plant growth and development, but is generally unavailable and inaccessible in soil, since applied P is mostly fixed to aluminium (Al) and ferrum (Fe) in acidic soils and to calcium (Ca) in alkaline soils. Increased organic acid excretion is thought to be one mechanism by which plants use to enhance P uptake. In this study, we overexpressed a mitochondrial malate dehydrogenase (MDH) gene from the mycorrhizal fungi Penicillium oxalicum in tobacco. The MDH activity of transgenic lines was significantly increased compared to that of wild type. Malate content in root exudation of transgenic lines induced in response to P deficiency was 1.3- to 2.9-fold greater than that of wild type under the same condition. Among the transgenic lines that were selected for analysis, one line (M1) showed the highest level of MDH activity and malate exudate. M1 showed a significant increase in growth over wild type, with 149.0, 128.5, and 127.9% increases in biomass, when grown in Al-phosphate, Fe-phosphate, and Ca-phosphate media, respectively. M1 also had better P uptake compared to wild type, with total P content increased by 287.3, 243.5, and 223.4% when grown in Al-phosphate, Fe-phosphate, and Ca-phosphate media, respectively. To our knowledge, this is the first study on improving the ability of a plant to utilize P from Al-phosphate, Fe-phosphate, and Ca-phosphate by manipulating the organic acid metabolism of the plant through genetic engineering.