The high-temperature cubic phase of SrCoO3−δ is a promising cathode material for solid oxide fuel cells (SOFC) due to its high electrical conductivity and oxygen permeation flux. However, this phase is not stable below 900 °C where a 3C-cubic to 2H-hexagonal phase transition takes place when the sample is slowly cooled down. In this work we have stabilized a 3C-tetragonal P4/mmm structure for SrCo1−xNbxO3−δ with x = 0.05. We have followed the strategy consisting of introducing a highly-charged cation at the Co sublattice, in order to avoid the stabilization of the unwanted 2H structure containing face-sharing octahedra. The characterization of this oxide included X-ray (XRD) and neutron powder diffraction (NPD) experiments. SrCo0.95Nb0.05O3−δ adopts a tetragonal superstructure of perovskite with a = a0, c = 2a0 (a0 ≈ 3.9 Å) defined in the P4/mmm space group containing two inequivalent Co positions. Flattened and elongated (Co,Nb)O6 octahedra alternate along the c axis sharing corners in a three-dimensional array (3C-like structure). In the test cell, the electrodes were supported on a 300-μm-thick pellet of the electrolyte La0.8Sr0.2Ga0.83Mg0.17O3−δ (LSGM). The test cells gave a maximum power density of 0.4 and 0.6 W/cm2 for temperatures of 800 and 850 °C, respectively, with pure H2 as fuel and air as oxidant. The good performance of this material as a cathode is related to its mixed electronic-ionic conduction (MIEC) properties, which can be correlated to the investigated structural features: the Co3+/Co4+ redox energy at the top of the O-2p bands accounts for the excellent electronic conductivity, which is favored by the corner-linked perovskite network. The considerable number of oxygen vacancies, with the oxygen atoms showing high displacement factors suggests a significant ionic mobility.