Magnetic cooling could be a radically different energy solution substituting conventional vapour compression refrigeration in the future. For the largest cooling effects of most potential refrigerants we need to fully exploit the different degrees of freedom such as magnetism and crystal structure. We report now for Heusler-type Ni-Mn-In-(Co) magnetic shape-memory alloys, the adiabatic temperature change Delta T-ad = 3.6 to -6.2 K under a moderate field of 2 T. Here it is the structural transition that plays the dominant role towards the net cooling effect. A phenomenological model is established that reveals the parameters essential for such a large Delta T-ad. We also demonstrate that obstacles to the application of Heusler alloys, namely the usually large hysteresis and limited operating temperature window, can be overcome by using the multi-response to different external stimuli and/or fine-tuning the lattice parameters, and by stacking a series of alloys with tailored magnetostructural transitions.