Photoinduced phase transitions in correlated materials promise diverse applications from ultrafast switches to optoelectronics. Resolving those transitions and possible metastable phases temporally are key enablers for these applications, but challenge existing experimental approaches. Extreme nonlinear optics can help probe phase changes, as higher-order nonlinearities have higher sensitivity and temporal resolution to band structure and lattice deformations. Here the ultrafast transition from the semiconducting to the metallic phases in polycrystalline thin-film NbO_{2} is investigated by time-resolved harmonic spectroscopy. The emission strength of all harmonic orders shows a steplike suppression when the excitation fluence exceeds a threshold (∼11-12 mJ/cm^{2}), below the fluence required for the thermal transition-a signature of the nonthermal emergence of a metallic phase within 100±20 fs. This observation is backed by full ab initio simulations as well as a 1D chain model of high-harmonic generation from both phases. Our results demonstrate femtosecond harmonic probing of phase transitions and nonthermal dynamics in solids.