The effect of cobalt substitution by highly charged Mo6+ cations in SrCo0.8Fe0.2O3-delta (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 SrCo(0.8-x)Fe(0.2)MoxO(3-delta) (SCFM) materials was accompanied by nanostructuring with observed formation of nanosized domains with ordered oxygen vacancies. Equilibrium "3 - delta - lgpO(2) - T" diagrams showed that SCF doping by molybdenum leads to broadening of the P-1 (cubic perovskite phase) stability region. The obtained SCFM membrane materials possess improved phase stability in the intermediate temperature range (T< 700 degrees C) and low oxygen partial pressure (pO(2) < 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.