Membranes based on complex solid oxides with oxygen-ionic conductivity are widely used in high-temperature electrochemical devices such as fuel cells, electrolyzers, sensors, gas purifiers, etc. The performance of these devices depends on the oxygen-ionic conductivity value of the membrane. Highly conductive complex oxides with the overall composition of (La,Sr)(Ga,Mg)O3 have regained the attention of researchers in recent years due to the progress in the development of electrochemical devices with symmetrical electrodes. In this research, we studied how the introduction of iron cations into the gallium sublattice in (La,Sr)(Ga,Mg)O3 affects the fundamental properties of the oxides and the electrochemical performance of cells based on (La,Sr)(Ga,Fe,Mg)O3. It was found that the introduction of iron leads to an increase in the electrical conductivity and thermal expansion in an oxidizing atmosphere, while no such behavior was observed in a wet hydrogen atmosphere. The introduction of iron into a (La,Sr)(Ga,Mg)O3 electrolyte leads to an increase in the electrochemical activity of Sr2Fe1.5Mo0.5O6−δ electrodes in contact with the electrolyte. Fuel cell studies have shown that, in the case of a 550 µm-thick Fe-doped (La,Sr)(Ga,Mg)O3 supporting electrolyte (Fe content 10 mol.%) and symmetrical Sr2Fe1.5Mo0.5O6−δ electrodes, the cell exhibits a power density of more than 600 mW/cm2 at 800 °C.