As the oldest known magnetic material, magnetite (Fe3O4) has fascinated mankind for millennia. As the first oxide in which a relationship between electrical conductivity and fluctuating/localized electronic order was shown, magnetite represents a model system for understanding correlated oxides in general. Nevertheless, the exact mechanism of the insulator-metal, or Verwey, transition has long remained inaccessible. Recently, three-Fe-site lattice distortions called trimerons were identified as the characteristic building blocks of the low-temperature insulating electronically ordered phase. Here we investigate the Verwey transition with pump-probe X-ray diffraction and optical reflectivity techniques, and show how trimerons become mobile across the insulator-metal transition. We find this to be a two-step process. After an initial 300 fs destruction of individual trimerons, phase separation occurs on a 1.5±0.2 ps timescale to yield residual insulating and metallic regions. This work establishes the speed limit for switching in future oxide electronics.