The discovery of novel phases of matter is at the core of modern physics. In quantum materials, subtle variations in atomic-scale interactions can induce dramatic changes in macroscopic properties and drive phase transitions. Despite their importance, the mesoscale processes underpinning phase transitions often remain elusive because of the vast differences in timescales between atomic and electronic changes and thermodynamic transformations. Here, we photoinduce and directly observe with x-ray scattering an ultrafast enhancement of the structural long-range order in the archetypal Mott system V2O3. Despite the ultrafast change in crystal symmetry, the change of unit cell volume occurs an order of magnitude slower and coincides with the insulator-to-metal transition. The decoupling between the two structural responses in the time domain highlights the existence of a transient photoinduced precursor phase, which is distinct from the two structural phases present in equilibrium. X-ray nanoscopy reveals that acoustic phonons trapped in nanoscale blocks govern the dynamics of the ultrafast transition into the precursor phase, while nucleation and growth of metallic domains dictate the duration of the slower transition into the metallic phase. The enhancement of the long-range order before completion of the electronic transition demonstrates the critical role the non-equilibrium structural phases play during electronic phase transitions in correlated electrons systems.