Ba7Nb4MoO20-based hexagonal perovskite derivatives are promising oxygen-ion conductors for solid electrolytes in solid-oxide fuel cells and electrolysers. A thorough understanding of chemical substitution and its impact on structural features conducive to high ionic conductivity is fundamental for decreasing the operation temperature of such devices. Here, a new 7H polytype-based composition, namely Ba7Nb3.9−xVxMo1.1O20.05, is investigated to assess the effect of vanadium substitution. Structural changes upon V incorporation are studied using X-ray and neutron diffraction, as well as 51V and 93Nb solid-state nuclear magnetic resonance spectroscopy. For the undoped composition at room temperature, two distinct oxygen sites (O1 and O5) are found along the palmierite-like layer, corresponding to a mix of four- and six-fold coordination for adjacent M2 cations. At high temperature (527 °C), reorganization of oxygen results in the major occupation of O1 and four-fold (tetrahedral) coordination of the M2 cations. The same rearrangement is observed upon V-substitution, but already at room temperature. From 51V NMR, we identified a tetrahedral coordination for V5+ cations, indicating their preferential occupation of the M2 site. This preferential occupation by V5+ cations is correlated with increasing tetrahedral coordination of Nb5+ cations as observed from 93Nb NMR. Altogether, these observations indicate that V-substitution impacts the oxygen sublattice so as to mimic the high-temperature structure. Additionally, BVSE calculations demonstrate a decreasing energy barrier for O2− migration associated with the presence of vanadium in the structure. This conclusion corroborates the hypothesis that vanadium's propensity for a lower coordination number is beneficial for promoting high O2− mobility in this promising class of oxide-ion conductors.