We have measured the adiabatic second order elastic constants of two Ni-Mn-Ga magnetic shape memory crystals with different martensitic transition temperatures, using ultrasonic methods. The temperature dependence of the elastic constants has been followed across the ferromagnetic transition and down to the martensitic transition temperature. Within experimental errors no noticeable change in any of the elastic constants has been observed at the Curie point. The temperature dependence of the shear elastic constant C' has been found to be very different for the two alloys. Such a different behavior is in agreement with recent theoretical predictions for systems undergoing multi-stage structural transitions.