Significance Understanding the atomic-scale mechanism of crystallization is a fundamental issue in statistical mechanics and the basis for the synthesis of novel materials. We investigated the structures of single xenon nanoparticles at the early stage of formation by exploiting the femtosecond single-shot X-ray diffraction approach. We found the coexistence of a highly stacking-disordered structure and a stable face-centered cubic structure in the same single nanoparticles, suggesting that crystallization proceeds via an intermediate stacking-disordered phase. The results shine light on the early stages of condensed matter nucleation and demonstrate the effectiveness of the single-shot diffraction method for elucidating fast structural dynamics in atomic aggregates, feeding unique experimental information to nucleation and growth theory as well as to research and applications.