Ba₃NbMoO_8.5 has recently been demonstrated to exhibit competitive oxide ion conductivity and to be stable under reducing conditions, making it an excellent potential electrolyte for solid oxide fuel cells. We report here the first investigation of the local structure in Ba₃NbMoO_8.5, carried out using variable-temperature neutron total scattering and pair distribution function (PDF) analysis. This work reveals a significant degree of disorder in the material, even at ambient conditions, in both the cation and the anion arrangements and suggests the prevalence of the five-fold Nb/Mo coordination. In addition, high resolution powder X-ray diffraction data indicate that the temperature-dependent structural changes in Ba₃NbMoO_8.5 are due to a first order phase transition, and reveal a previously unreported effect of thermal history on the room-temperature form of the material. PDF modelling shows that Ba₃NbMoO_8.5 has an essentially continuous oxygen distribution in the ab plane at 600 °C which leads to its high oxide-ion conductivity.