Mechanical alloying of immiscible elements in the Fe–Mg system (≤32 at % Mg) is achieved by grinding in a planetary ball mill. The process is studied by x-ray diffraction, Mössbauer spectroscopy, and magnetic measurements. The results attest to the formation of supersaturated solid solutions of Mg in α-Fe. The highest Mg content of the solid solutions is 5–7 at %. Mössbauer results are used to evaluate the changes in the hyperfine magnetic field at Fe nuclei associated with the presence of one Mg atom among the nearest neighbors and next nearest neighbors of Fe in the solid solutions: ΔH1 = –1760 kA/m and ΔH2 = –800 kA/m, respectively. Increasing the Mg content of the starting mixture reduces Mg solubility in Fe. Thermodynamic analysis indicates that the driving force for the formation of solid solutions may be associated with the excess energy of coherent interfaces in the Fe–Mg nanocomposite resulting from mechanical alloying. The elastic strain arising from the lattice mismatch between Fe and Mg facilitates incorporation of Mg into α-Fe. Above a certain Mg content, no coherent interfaces are formed, and the thermodynamic driving force for Mg dissolution disappears. As a result, the system becomes immiscible.