A variable temperature neutron diffraction study of the novel oxide ion conductor Ba₃MoNbO_8.5 has been performed between 25 and 600 °C. Nonmonotonic behavior of the cell parameters, bond lengths, and angles are observed indicating a structural rearrangement above 300 °C. The oxygen/vacancy distribution changes as the temperature increases so that the ratio of (Mo/Nb)O₄ tetrahedra to (Mo/Nb)O₆ octahedra increases upon heating above 300 °C. A strong correlation between the oxide ionic conductivity and the number of (Mo/Nb)O₄ tetrahedra within the average structure of Ba₃MoNbO_8.5 is observed. The increase in the number of (Mo/Nb)O₄ tetrahedra upon heating from 300-600 °C most likely offers more low energy transition paths for transport of the O^2- ions enhancing the conductivity. The unusual structural rearrangement also results in relaxation of Mo(1)/Nb(1) and Ba(2) away from the mobile oxygen, increasing the ionic conductivity. The second order Jahn-Teller effect most likely further enhances the distortion of the MO₄/MO₆ polyhedra as distortions created by both electronic and structural effects are mutually supportive.