A systematic investigation examining the origins of structural distortions in rutile-related ternary uranium AUO4 oxides using a combination of high-resolution structural and spectroscopic measurements supported by ab initio calculations is presented. The structures of β-CdUO4, MnUO4, CoUO4, and MgUO4 are determined at high precision by using a combination of neutron powder diffraction (NPD) and synchrotron X-ray powder diffraction (S-XRD) or single crystal X-ray diffraction. The structure of β-CdUO4 is best described by space group Cmmm whereas MnUO4, CoUO4, and MgUO4 are described by the lower symmetry Ibmm space group and are isostructural with the previously reported β-NiUO4 [Murphy et al. Inorg. Chem. 2018, 57, 13847]. X-ray absorption spectroscopy (XAS) analysis shows all five oxides contain hexavalent uranium. The difference in space group can be understood on the basis of size mismatch between the A2+ and U6+ cations whereby unsatisfactory matching results in structural distortions manifested through tilting of the AO6 polyhedra, leading to a change in symmetry from Cmmm to Ibmm. Such tilts are absent in the Cmmm structure. Heating the Ibmm AUO4 oxides results in reduction of the tilt angle. This is demonstrated for MnUO4 where in situ S-XRD measurements reveal a second-order phase transition to Cmmm near T = 200 °C. Based on the extrapolation of variable temperature in situ S-XRD data, CoUO4 is predicted to undergo a continuous phase transition to Cmmm at ∼1475 °C. Comparison of the measured and computed data highlights inadequacies in the DFT+U approach, and the conducted analysis should guide future improvements in computational methods. The results of this investigation are discussed in the context of the wider AUO4 family of oxides.