The crystal chemistry and oxygen conductivity of vanadium-doped apatites of nominal composition [La8AE2][Ge6−xVx]O26+x/2 (AE = Ca, Sr, Ba; 0 ≤ x ≤ 1.5) were studied to establish their potential as intermediate temperature solid oxide fuel cell (SOFC) electrolytes. Single-phase products obtained for x ≤ 0.5 were found, using a combination of powder synchrotron X-ray and neutron diffraction, to be P63/m apatites. The ionic conductivities extracted by complex impedance spectroscopy showed that small vanadium amendments enhanced oxygen mobility at intermediate temperatures (500–700 °C) by more than one order of magnitude, as the incorporation of V5+ through displacement of Ge4+ is charge balanced with interstitial O2− that improves ionic conduction. The most promising composition was La7.88Ca2Ge5.35V0.65O26.15 that delivered σ = 3.44 × 10−4 S cm−1 at 500 °C. The superstoichiometric oxygen was delocalised, without fixed X-ray or neutron scattering centres. Crystal chemistry systematics demonstrate that the Ca-apatite was superior because the relatively small framework expanded the tunnel through reduced (La/AE)O6 metaprism twisting (φ), ensuring the P63/m symmetry was adopted, which favours the passage of O2− with lower activation energy.