Bimetallic nanoparticles are often superior candidates for a wide range of technological and biomedical applications owing to their enhanced catalytic, optical, and magnetic properties, which are often better than their monometallic counterparts. Most of their properties strongly depend on their chemical composition, crystallographic structure, and phase distribution. However, little is known of how their crystal structure, on the nanoscale, transforms over time at elevated temperatures, even though this knowledge is highly relevant in case nanoparticles are used in, e.g., high-temperature catalysis. Au-Fe is a promising bimetallic system where the low-cost and magnetic Fe is combined with catalytically active and plasmonic Au. Here, we report on the in situ temporal evolution of the crystalline ordering in Au-Fe nanoparticles, obtained from a modern laser ablation in liquids synthesis. Our in-depth analysis, complemented by dedicated atomistic simulations, includes a detailed structural characterization by X-ray diffraction and transmission electron microscopy as well as atom probe tomography to reveal elemental distributions down to a single atom resolution. We show that the Au-Fe nanoparticles initially exhibit highly complex internal nested nanostructures with a wide range of compositions, phase distributions, and size-depended microstrains. The elevated temperature induces a diffusion-controlled recrystallization and phase merging, resulting in the formation of a single face-centered-cubic ultrastructure in contact with a body-centered cubic phase, which demonstrates the metastability of these structures. Uncovering these unique nanostructures with nested features could be highly attractive from a fundamental viewpoint as they could give further insights into the nanoparticle formation mechanism under non-equilibrium conditions. Furthermore, the in situ evaluation of the crystal structure changes upon heating is potentially relevant for high-temperature process utilization of bimetallic nanoparticles, e.g., during catalysis.