The origin of the 2-order of magnitude difference in the proton conductivity of the hydrated forms of hexagonal and cubic oxygen deficient BaScxTi1-xO3-δ (x = 0.2 and x = 0.7) was probed using a combination of neutron diffraction and density functional theory techniques to support published X-ray diffraction, conductivity, thermogravimetric and differential scanning calorimetry studies. Cation ordering is found in the 6H structure type (space group P63/mmc) adopted by BaSc0.2Ti0.8O3-δ with scandium preferentially substituting in the vertex sharing octahedra (2a crystallographic site) and avoiding the face-sharing octahedra (4f site). This is coupled with oxygen vacancy ordering in the central plane of the face-sharing octahedra (O1 site). In BaSc0.7Ti0.3O3-δ a simple cubic perovskite (space group Pm3[combining macron]m) best represents the average structure from Rietveld analysis with no evidence of either cation ordering or oxygen vacancy ordering. Significant diffuse scattering is observed, indicative of local order. Hydration in both cases leads to complete filling of the available oxygen vacancies and permits definition of the proton sites. We suggest that the more localised nature of the proton sites in the 6H structure is responsible for the significantly lower proton conduction observed in the literature. Within the 6H structure type final model, proton diffusion requires a 3-step process via higher energy proton sites that are unoccupied at room temperature and is also likely to be anisotropic whereas the highly disordered cubic perovskite proton position allows 3-dimensional diffusion by well-described modes. Finally, we propose how this knowledge can be used to further materials design for ceramic electrolytes for proton conducting fuel cells.