Herein, a mechanism is proposed as to how thin films formed from a Heusler compound can simultaneously have both perpendicular magnetic anisotropy (PMA) and be half-metallic. It is proposed that a thin film formed from a half-metallic full-Heusler or half-Heusler compound that is cubic in the bulk can undergo a tetragonal distortion by adopting the lattice constant of the underlayer material during the thin film deposition process. The value of this distortion can be tuned by using underlayer materials with different in-plane lattice constants. The distortion can thereby be optimized so that it is large enough to give rise to sufficient PMA, while, simultaneously, small enough to retain the half-metallic properties (and, therefore, high tunneling magnetoresistance properties) of the Heusler compound. Density functional theory (DFT) calculations that are carried out for 90 full-Heuslers and 147 half-Heuslers that have been identified in the literature as half-metals show that of these, 14 full-Heusler and 59 half-Heusler compounds display both half-metallicity and PMA for optimal tetragonal distortions.