Iron and magnesium are almost immiscible at ambient pressure. The low solubility of Mg in Fe is due to a very large size mismatch between the alloy components. However, the compressibility of Mg is much higher than that of Fe, and therefore the difference in atomic sizes between elements decreases dramatically with pressure. Based on the predictions of ab initio calculations, we demonstrate in a series of experiments in a multianvil apparatus and in electrically and laser-heated diamond anvil cells that high pressure promotes solubility of magnesium in iron. At the megabar pressure range, more than 10 at. % of Mg can dissolve in Fe and then the alloy can be quenched to ambient conditions. A generality of the concept of high-pressure alloying between immiscible elements is demonstrated by its application to two other Fe group elements, Co and Ni.