Many ultrafast solid phase transitions are treated as chemical reactions that transform the structures between two different unit cells along a reaction coordinate, but this neglects the role of disorder. Although ultrafast diffraction provides insights into atomic dynamics during such transformations, diffraction alone probes an averaged unit cell and is less sensitive to randomness in the transition pathway. Using total scattering of femtosecond x-ray pulses, we show that atomic disordering in photoexcited vanadium dioxide (VO) is central to the transition mechanism and that, after photoexcitation, the system explores a large volume of phase space on a time scale comparable to that of a single phonon oscillation. These results overturn the current understanding of an archetypal ultrafast phase transition and provide new microscopic insights into rapid evolution toward equilibrium in photoexcited matter.