The structures and high-temperature phase transition of CaUNb2O8 were studied in situ using synchrotron X-ray and neutron powder diffraction. Rietveld refinements provided an accurate description of the crystal structures of both the monoclinic fergusonite-type I2/b structure observed at room temperature and the tetragonal scheelite-type I41/a structure found at high temperatures. Bond valence sum analysis showed Nb5+ to be octahedrally coordinated in the monoclinic fergusonite-type structure, akin to other ANbO4 materials. Rietveld analysis of the variable temperature data allowed for the determination of accurate unit cell parameters and atomic coordinates, as well as revealing a reversible phase transition around ∼750 °C. The Nb-O bond distances display anomalous behavior, with a discontinuity in the longer Nb-O(1') distance coinciding with the phase transition suggestive of a reconstructive phase transition. Mode analysis identified the Γ2+ mode as the primary mode that drives the phase transition; this is linearly coupled to the induced spontaneous strain within the monoclinic fergusonite-type structure. Analysis of the temperature dependence of the Nb(z) positional parameter, as well as of the ϵ1-ϵ2 and ϵ6 strain parameters, showed that the phase transition is not strictly second order, with the critical exponent β ≠ 1/2. This study demonstrates the complex structural features of mixed cation metal oxides at elevated temperatures.