FeO_x, SrFeO_3-y (SF), and Ba_0.5Sr_0.5FeO_3−y (BSF) were studied for application as fuel oxidation catalysts in solid oxide fuel cells (SOFC) anodes. Electrodes were prepared by impregnation into porous yttria-stabilized zirconia (YSZ), with La_0.3Sr_0.7TiO_3−y (LST) added for electronic conductivity. The electrode impedances decreased dramatically upon addition of SF and BSF and much less when only SrO or FeO_x were added. Temperature Programmed Desorption (TPD) of O₂ from oxidized BSF showed O₂ desorbing between 200 °C and 700 °C, while no O₂ desorbed from Fe₂O₃ below 900 °C. The results, together with thermodynamic analysis, suggest that stabilization of Fe⁺⁴ in the perovskite lattice plays an important role in enhancing the catalytic activity of SF and BSF by providing access to a Fe³⁺/Fe⁴⁺ redox couple that can accept oxygen anions from the yttria-stabilized zirconia (YSZ) electrolyte. Oxygen is weakly bound to these sites facilitating its reaction with adsorbed H₂.