Hydroxyapatite (HAP) is the main mineral component of bones and teeth. It is widely used in medicine as a bone filler and coating for implants to promote new bone growth. Ion substitutions into the HAP structure highly affect its properties. One of the most important substituents is magnesium. This paper presents new results obtained using high-precision hybrid density functional theory calculations for Mg/Ca substitutions in HAP in a wide magnesium concentration range within a 2 × 2 × 2 supercell model. Experimental data on the mechanochemical synthesis of HAP-Mg samples with different Mg concentrations are also presented. A comparison between the experiment and the theory showed good agreement: the HAP-Mg unit cell parameters and volume decreased with increasing degree of Mg/Ca substitution. The changes in the distances between the Ca and O, Ca and H, and Mg and O ions upon Mg/Ca substitution in different calcium positions was analyzed. The resulting asymmetry and distortion of the cell parameters were evaluated. It was shown that bulk modulus, energy levels, and band gap depend on the degree of Mg substitutions in the Ca1 and Ca2 positions. The formation energies of Mg/Ca substitutions showed non-monotonic behavior that was different for Ca1 and Ca2 positions. The Ca2 position had a slightly higher probability (~5 meV/f.u.) of substitution than Ca1 position at a Mg concentration x = 0.5. At x = 1, substitution in both positions can coexist. The simulated IR spectra for different Mg/Ca substitutions showed that Mg in the Ca2 position changes the IR spectrum more significantly than Mg in the Ca1 position. Similar changes were recorded in the IR spectra of the synthesized samples. The electronic structure is shown to be sensitive to the number and position of substitutions, which may be used to tweak the optical properties of the HAP-Mg material.