Crystallization is a fundamental natural phenomenon and the ubiquitous physical process in materials science for the design of new materials. So far, experimental observations of the structural dynamics in crystallization have been mostly restricted to slow dynamics. We present here an exclusive way to explore the dynamics of crystallization in highly controlled conditions (i.e., in the absence of impurities acting as seeds of the crystallites) as it occurs in vacuum. We have measured the early formation stage of solid Xe nanoparticles nucleated in an expanding supercooled Xe jet by means of an X-ray diffraction experiment with 10-fs X-ray free-electron laser (XFEL) pulses. We found that the structure of Xe nanoparticles is not pure face-centered cubic (fcc), the expected stable phase, but a mixture of fcc and randomly stacked hexagonal close-packed (rhcp) structures. Furthermore, we identified the instantaneous coexistence of the comparably sized fcc and rhcp domains in single Xe nanoparticles. The observations are explained by the scenario of structural aging, in which the nanoparticles initially crystallize in the highly stacking-disordered rhcp phase and the structure later forms the stable fcc phase. The results are reminiscent of analogous observations in hard-sphere systems, indicating the universal role of the stacking-disordered phase in nucleation.