In this work, effects of molybdenum doping on the crystal structure, stability, electrical conductivity, oxygen permeability and thermomechanical properties of Sr(Fe,Al)O3–δ-based perovskites, were studied. The electrochemical performance of model anodes of solid oxide fuel cells (SOFCs), made of SrFe0.7Mo0.3O3–δ, was assessed. Whilst the introduction of Mo cations improves structural stability with respect to the oxygen vacancy ordering processes, excessive molybdenum content leads to a worse phase and mechanical stability under oxidizing conditions. Mo-doping was shown to decrease the thermal and chemical expansivity, to reduce p-type electronic conductivity and to increase n-type electronic conduction. The oxygen permeation fluxes through gas-tight Sr0.97Fe0.75Al0.2Mo0.05O3–δ membranes are determined by both the bulk oxygen diffusion and surface exchange kinetics. The role of the latter factor increases on decreasing temperature and reducing oxygen partial pressure. Due to a relatively high electrical conductivity and moderate thermal expansion coefficients in reducing conditions, SrFe0.7Mo0.3O3–δ-based anodes show a substantially high electrochemical activity.