With a view to the design of hard magnets without rare earths we explore the possibility of large magnetocrystalline anisotropy energies in Heusler compounds that are unstable with respect to a tetragonal distortion. We consider the Heusler compounds Fe₂YZ with Y = (Ni, Co, Pt), and Co₂YZ with Y = (Ni, Fe, Pt) where, in both cases, Z = (Al, Ga, Ge, In, Sn). We find that for the Co₂NiZ, Co₂PtZ, and Fe₂PtZ families the cubic phase is always, at T = 0, unstable with respect to a tetragonal distortion, while, in contrast, for the Fe₂NiZ and Fe₂CoZ families this is the case for only 2 compounds - Fe₂NiGe and Fe₂NiSn. For all compounds in which a tetragonal distortion occurs we calculate the magnetocrystalline anisotropy energy (MAE) finding remarkably large values for the Pt containing Heuslers, but also large values for a number of the other compounds (e.g. Co₂NiGa has an MAE of -2.38 MJ m⁻³). The tendency to a tetragonal distortion we find to be strongly correlated with a high density of states (DOS) at the Fermi level in the cubic phase. As a corollary to this fact we observe that upon doping compounds for which the cubic structure is stable such that the Fermi level enters a region of high DOS, a tetragonal distortion is induced and a correspondingly large value of the MAE is then observed.