Uranium dioxide (UO2) is the major nuclear fuel component of fission power reactors. A key concern during severe accidents is the melting and leakage of radioactive UO2 as it corrodes through its zirconium cladding and steel containment. Yet, the very high temperatures (>3140 kelvin) and chemical reactivity of molten UO2 have prevented structural studies. In this work, we combine laser heating, sample levitation, and synchrotron x-rays to obtain pair distribution function measurements of hot solid and molten UO2. The hot solid shows a substantial increase in oxygen disorder around the lambda transition (2670 K) but negligible U-O coordination change. On melting, the average U-O coordination drops from 8 to 6.7 ± 0.5. Molecular dynamics models refined to this structure predict higher U-U mobility than 8-coordinated melts.