Magnesium, as one of the most abundant cations in the human body, plays an important role in both physiological and pathological processes. In this study, it was shown that a promising biomedical material, Mg-substituted hydroxyapatite (Mg-HA), can be synthesized via a fast mechanochemical method. For this method, the nature of magnesium-containing carriers was shown to be important. When using magnesium oxide as a source of magnesium, the partial insertion of magnesium cations into the apatite structure occurs. In contrast, when magnesium hydroxide or monomagnesium phosphate is used, single-phase Mg-HA is formed. Both experimental and theoretical investigations showed that an increase in the Mg content leads to a decrease in the lattice parameters and unit cell volume of Mg-HA. Density functional theory calculations showed the high sensitivity of the lattice parameters to the crystallographic position of the calcium site substituted by magnesium. It was shown experimentally that the insertion of magnesium cations decreases the thermal stability of hydroxyapatite. The thermal decomposition of Mg-HA leads to the formation of a mixture of stoichiometric HA, magnesium oxide, and Mg-substituted tricalcium phosphate phases.