The effect of cobalt substitution by highly charged Mo6+ cations in SrCo0.8Fe0.2O3-δ (SCF) on the structure, microstructure, oxygen permeation performance and stability in the atmosphere containing carbon dioxide was systematically investigated by XRD, HT-XRD, Mossbauer spectroscopy, oxygen release technique and oxygen permeation experiments. The decrease in oxygen stoichiometry of SrCo0.8-xFe0.2MoxO3-δ (SCFM) materials was accompanied by nanostructuring with observed formation of nanosized domains with ordered oxygen vacancies. Equilibrium “3−δ−lg pO2−T” diagrams showed that SCF doping by molybdenum leads to broadening of the P1 (cubic perovskite phase) stability region. The obtained SCFM membrane materials possess improved phase stability in the intermediate temperature range (T < 700 °C) and low oxygen partial pressure (pO2 < 0.06 atm) compared to the undoped SCF oxide. The observed non-Arrhenius dependence of oxygen fluxes across SCFM disc membranes is related to combined control by bulk diffusion and surface exchange reactions.