A class of double-perovskite compounds display fast oxygen ion diffusion and high catalytic activity toward oxygen reduction while maintaining excellent compatibility with the electrolyte. The astoundingly extended stability of NdBa1−xCaxCo2O5+δ (NBCaCO) under both air and CO2-containing atmosphere is reported along with excellent electrochemical performance by only Ca doping into the A site of NdBaCo2O5+δ (NBCO). The enhanced stability can be ascribed to both the increased electron affinity of mobile oxygen species with Ca, determined through density functional theory calculations and the increased redox stability from the coulometric titration.