A new concept of an "oxygen shuttle" type battery for Mg-air solid oxide batteries using a Ca-stabilized ZrO2 electrolyte was proposed and studied. The observed open circuit potential and discharge capacity were 1.81 V and 1154 mA h gMg(-1) (52% of the theoretical capacity), respectively.