We demonstrate ultrafast dephasing in the random transport of light through a layer consisting of strongly scattering GaP nanowires. Dephasing results in a nonlinear intensity modulation of individual pseudomodes which is 100 times larger than that of bulk GaP. Different contributions to the nonlinear response are separated by using total transmission, white-light frequency correlation, and statistical pseudomode analysis. A dephasing time of 1.2±0.2¿¿ps is found. Quantitative agreement is obtained with numerical model calculations which include photoinduced absorption and deformation of individual scatterers. Nonlinear dephasing of photonic eigenmodes opens up avenues for ultrafast control of random lasers, nanophotonic switches, and photon localization.