We propose a high-temperature, rechargeable metal-air battery that relies on Ti or Zr metal as the anode and the shuttling of oxygen anions between the cathode and the anode through a solid-oxide ion-conducting electrolyte. The cathode has much in common with solid-oxide fuel cells. Key in the proposed battery is the use of Ti or Zr as the anode as these metals are unique in their ability to dissolve oxygen up to concentrations of 33% with minimal structural and volumetric changes. First-principles statistical mechanics calculations predict open circuit voltages around 2.5 V, substantially larger than the open circuit voltage of high-temperature solid-oxide fuel cells. The calculations predict the stability of TiO and ZrO monoxides along with TiOx and ZrOx (with x as high as 1/2) solid solutions. These suboxide phases are all predicted to be metallic, indicating that electron transport in the anodes will not be rate limiting. The oxygen diffusion coefficients in the Ti and Zr suboxides at high temperature (similar to 700-800 degrees C) are predicted to be comparable to that of Li ions in intercalation compounds. These properties suggest theoretical capacities as high as 840 mAh g(-1) and 500 mAh g(-1) for Ti and Zr based metal-air batteries respectively. (C) 2013 Elsevier B.V. All rights reserved.