Oxide ion conductors are important materials with a range of technological applications and are currently used as electrolytes for solid oxide fuel cells and solid oxide electrolyzer cells. Here we report the crystal structure and electrical properties of the hexagonal perovskite derivative Ba3MoNbO8.5. Ba3MoNbO8.5 crystallizes in a hybrid of the 9R hexagonal perovskite and palmierite structures. This is a new and so far unique crystal structure that contains a disordered distribution of (Mo/Nb)O6 octahedra and (Mo/Nb)O4 tetrahedra. Ba3MoNbO8.5 shows a wide stability range and exhibits predominantly oxide ion conduction over a pO2 range from 10-20 to 1 atm with a bulk conductivity of 2.2 × 10-3 S cm-1 at 600 °C. The high level of conductivity in a new structure family suggests that further study of hexagonal perovskite derivatives containing mixed tetrahedral and octahedral geometry could open up new horizons in the design of oxygen conducting electrolytes.