The recently developed solid oxide metal-air redox battery is a new technology capable of high-rate chemistry. Here we report that the performance, reversibility and stability of a solid oxide iron-air redox battery can be significantly improved by nanostructuring energy storage materials from a carbothermic reaction.