For the development of proton-based electrolytes, high proton conductivity at intermediate temperatures (300-600 degrees C) is crucial, but the available materials have been confined to a limited number of the structure families, such as cubic perovskites. Herein, we report Ba5Er2Al2ZrO13, a hexagonal perovskite-related oxide, as a new class of proton conductors exhibiting higher conductivities than 10(-3) S cm(-1) between 300 and 1200 degrees C. The protons as charge carriers are found to exist in the inherently oxygen-deficient h' layer of Ba5Er2Al2ZrO13, which are supported by Rietveld analysis of neutron-diffraction data, bond-valence-based energy calculations, and thermogravimetric analysis. Our discovery of a new structure family of proton conductors with the inherently oxygen-deficient h' layer offers a strategy in designing superior proton conductors based on hexagonal perovskite-related oxides.