The novel Fe/Nb co-substituted SrCo1−2x(Fe,Nb)xO3−δ (x = 0.05, 0.10) oxides have been synthesized and characterized by X-ray diffraction (XRD), differential scanning calorimetry (DSC), thermogravimetry (TG), and scanning electron microscopy (SEM). The XRD and DSC results demonstrate that the structural stability of the Fe/Nb co-substituted samples x = 0.05, 0.10 is improved greatly compared to the sample x = 0.00. The Fe/Nb co-doping in the SrCoO3−δ oxide results in the improved structural stability of the SrCo1−2x(Fe,Nb)xO3−δ (x = 0.05, 0.10) oxides. The nonstoichiometric and sintering properties were investigated by TG and SEM, and the oxygen permeation fluxes were measured at 800–950 °C for the sample x = 0.10. The improved oxygen permeability of the ceramic SrCo1−2x(Fe,Nb)xO3−δ (x = 0.10) membrane compared to the (Ba0.5Sr0.5)(Co0.8Fe0.2)O3−δ and SrCo0.8Fe0.2O3–δ membranes, was observed under an air/He oxygen partial pressure gradient at 800–950 °C.