Oxide-ion conductors are important in various applications such as solid-oxide fuel cells. Although zirconia-based materials are widely utilized, there remains a strong motivation to discover electrolyte materials with higher conductivity that lowers the working temperature of fuel cells, reducing cost. Oxide-ion conductors with hexagonal perovskite related structures are rare. Herein, we report oxide-ion conductors based on a hexagonal perovskite-related oxide Ba7Nb4MoO20. Ba7Nb3.9Mo1.1O20.05 shows a wide stability range and predominantly oxide-ion conduction in an oxygen partial pressure range from 2 × 10-26 to 1 atm at 600 °C. Surprisingly, bulk conductivity of Ba7Nb3.9Mo1.1O20.05, 5.8 × 10-4 S cm-1, is remarkably high at 310 °C, and higher than Bi2O3- and zirconia-based materials. The high conductivity of Ba7Nb3.9Mo1.1O20.05 is attributable to the interstitial-O5 oxygen site, providing two-dimensional oxide-ion O1-O5 interstitialcy diffusion through lattice-O1 and interstitial-O5 sites in the oxygen-deficient layer, and low activation energy for oxide-ion conductivity. Present findings demonstrate the ability of hexagonal perovskite related oxides as superior oxide-ion conductors.