Materials with the apatite structure have a range of important applications in which their function is influenced by details of their local structure. Here, we describe an average and local structural study to probe the origins of high-temperature oxide ion mobility in La-10(Ge-04)(6)O-3 and La8Bi2(GeO4)(6)O-3 oxygen-excess materials, using the low-conductivity interstitial oxide-free La8Sr2(GeO4)(6)O-2 as a benchmark. For La-10, and La8Bi2, we locate the interstitial oxygen, O-int, responsible for conductivity by Rietveld refinement and relate the P6(3)/m to P (1) over bar phase transitions on cooling to oxygen ordering. Local structural studies using neutron total scattering reveal that well-ordered GeO5 square pyramidal groups form in the structure at low temperature, but that O-int becomes significantly more disordered in the high-conductivity, high-temperature structures, with a transition to more trigonal-bipyramid-like average geometry. We relate the higher conductivity of Bi materials to the presence of several O-int sites of similar energy in the structure, which correlates with its less-distorted low-temperature average structure.