Femtosecond laser pulses have opened new frontiers for the study of ultrafast phase transitions and nonequilibrium states of matter. In this Letter, we report on structural dynamics in atomic clusters pumped with intense near-infrared (NIR) pulses into a nanoplasma state. Employing wide-angle scattering with intense femtosecond x-ray pulses from a free-electron laser source, we find that highly excited xenon nanoparticles retain their crystalline bulk structure and density in the inner core long after the driving NIR pulse. The observed emergence of structural disorder in the nanoplasma is consistent with a propagation from the surface to the inner core of the clusters.