Uranium (U) is a ubiquitous element in the Earth's crust at similar to 2 ppm. In anoxic environments, soluble hexavalent uranium (U(VI)) is reduced and immobilized. The underlying reduction mechanism is unknown but likely of critical importance to explain the geochemical behavior of U. Here, we tackle the mechanism of reduction of U(VI) by the mixed-valence iron oxide, magnetite. Through high-end spectroscopic and microscopic tools, we demonstrate that the reduction proceeds first through surface-associated U(VI) to form pentavalent U, U(V). U(V) persists on the surface of magnetite and is further reduced to tetravalent UO2 as nanocrystals (similar to 1-2nm) with random orientations inside nanowires. Through nanoparticle re-orientation and coalescence, the nanowires collapse into ordered UO2 nanoclusters. This work provides evidence for a transient U nanowire structure that may have implications for uranium isotope fractionation as well as for the molecular-scale understanding of nuclear waste temporal evolution and the reductive remediation of uranium contamination.