While commercial Li-ion batteries offer the highest energy densities of current rechargeable battery technologies, their energy storage limit has almost been achieved. Therefore, there is considerable interest in Mg batteries, which could offer increased energy densities in comparison to Li-ion batteries if a high-voltage electrode material, such as a transition-metal oxide, can be developed. However, there are currently very few oxide materials which have demonstrated reversible and efficient Mg2+ insertion and extraction at high voltages; this is thought to be due to poor Mg2+ diffusion kinetics within the oxide structural framework. Herein, the authors provide conclusive evidence of electrochemical insertion of Mg2+ into the tetragonal tungsten bronze V4Nb18O55, with a maximum reversible electrochemical capacity of 75 mA h g-1, which corresponds to a magnesiated composition of Mg4V4Nb18O55. Experimental electrochemical magnesiation/demagnesiation revealed a large voltage hysteresis with charge/discharge (1.12 V vs Mg/Mg2+); when magnesiation is limited to a composition of Mg2V4Nb18O55, this hysteresis can be reduced to only 0.5 V. Hybrid-exchange density functional theory (DFT) calculations suggest that a limited number of Mg sites are accessible via low-energy diffusion pathways, but that larger kinetic barriers need to be overcome to access the entire structure. The reversible Mg2+ intercalation involved concurrent V and Nb redox activity and changes in crystal structure, as confirmed by an array of complementary methods, including powder X-ray diffraction, X-ray absorption spectroscopy, and energy-dispersive X-ray spectroscopy. Consequently, it can be concluded that the tetragonal tungsten bronzes show promise as intercalation electrode materials for Mg batteries.