Based on high-throughput density functional theory calculations, we investigated the effects of light interstitial H, B, C, and N atoms on the magnetic properties of cubic Heusler alloys, with the aim to design new rare-earth free permanent magnets. It is observed that the interstitial atoms induce significant tetragonal distortions, leading to 32 candidates with large ($>$ 0.4 MJ/m$^3$) uniaxial magneto-crystalline anisotropy energies (MAEs) and 10 cases with large in-plane MAEs. Detailed analysis following the the perturbation theory and chemical bonding reveals the strong MAE originates from the local crystalline distortions and thus the changes of the chemical bonding around the interstitials. This provides a valuable way to tailor the MAEs to obtain competitive permanent magnets, filling the gap between high performance Sm-Co/Nd-Fe-B and widely used ferrite/AlNiCo materials.