The Prototypical magnetic memory shape alloy Ni$_2$MnGa undergoes various phase transitions as a function of temperature, pressure, and doping. In the low-temperature phases below 260 K, an incommensurate structural modulation occurs along the [110] direction which is thought to arise from softening of a phonon mode. It is not at present clear how this phenomenon is related, if at all, to the magnetic memory effect. Here we report time-resolved measurements which track both the structural and magnetic components of the phase transition from the modulated cubic phase as it is brought into the high-symmetry phase. The results suggest that the photoinduced demagnetization modifies the Fermi surface in regions that couple strongly to the periodicity of the structural modulation through the nesting vector. The amplitude of the periodic lattice distortion, however, appears to be less affected by the demagnetizaton.