Calcium sulfate-based powders with magnesium substituting for calcium cations in amounts of 10, 20, and 40 mol % were synthesized by the mechanochemical method. The phase composition of the products, the solubility, and the compressive strength of the obtained cement materials mixed with water were studied. It was shown that the solubility in the physiological saline increases, while the strength of set cements decreases with increasing degree of substitution. The materials are applicable for bone grafting in surgery, for fabrication of composite biomaterials, and as carriers for targeted drug delivery in the human body.