In magnetoplasmonics, it is possible to tailor the magneto-optical properties of nanostructures by exciting surface plasmon polaritons (SPPs). Thus far, magnetoplasmonic effects have been considered static. Here, we describe ultrafast manifestations of magnetoplasmonics by observing the non-trivial evolution of the transverse magneto-optic Kerr effect within 45-fs pulses reflected from an iron-based magnetoplasmonic crystal. The effect occurs for resonant SPP excitations, displays opposite time derivative signs for different slopes of the resonance, and is explained with the magnetization-dependent dispersion relation of SPPs.