We report a substantial enhancement of the oxide-ion conductivity in Sr11Mo4O23 achieved by Nb doping the Mo sites. This series responds to the formula: Sr11Mo4-xNbxO23-δ (with x = 0.0, 0.5 and 1.0). The original structure can be related to the conventional double perovskite; however, it presents a broken corner sharing connectivity of the octahedral framework, hence leading to a complex and highly defective network. The samples were prepared via citrate precursor method, followed by thermal treatments at 1300 °C for 12 hours in air. The crystal structures were refined from X-ray and neutron powder diffraction (NPD) data. A phase transition from tetragonal to cubic symmetry is identified in a temperature-dependent NPD study, driven by an oxygen delocalization effect. The ionic conductivity measured by impedance spectroscopy is enhanced upon Nb-doping; the x = 1 doped phase exhibits a threefold increase compared to the pristine Sr11Mo4O23 oxide, with conductivity values of 7.6 × 10-3 and 2.7 × 10-2 S·cm-1 at 650 and 800 °C, which are even greater than for YSZ in the 650-800 °C temperature range, and close to those reported for other state-of-the art solid-oxide electrolytes.