Power and energy dependences of magnesium air batteries on the materials and structures of carbon cathodes are investigated for the purpose of developing a high power Mg-air battery. It is found that three-phase co-existing interface plays an important role to improve the power and energy properties. A new cathode structure having an enhanced cathode reaction was produced. The Mg-air battery with this new cathode generated 5 times more power and 2.5 times more energy, compared to that of conventional cathodes. Moreover, the cathode with a three-layered structure was fabricated for obtaining a better current density. The high power battery cell showed 72 W/kg of power density and 400 Wh/kg of energy density, which revealed a potential ability for various application, such as mobile phone, electric vehicle, and high power emergency power supply.