In this study, we used a novel composite material based on magnesium phosphate cement (MPC) to explore the retention of fluoride from used water. Dead-burned magnesium oxide (MgO), ammonium dihydrogen phosphate (NH4H2PO4), and a few retarders were used to create this particular substance. Several studies have corroborated the performance of using aluminum in the capture of fluoride. From this perspective, we attempted to reinforce our matrix with different quantities of aluminum, which increased the resistance of the composite in water. The optimal conditions that were obtained were evaluated and scrutinized using a range of techniques, including scanning electron microscopy (SEM), X-ray diffraction (XRD), thermogravimetric analysis (TGA), Fourier transforms infrared spectroscopy (FTIR), and Brunauer–Emmett–Teller (BET). The adsorbents demonstrated a powerful ability to remove fluoride from contaminated water and the defluoridation capacity was evaluated at 4.84 mg/g. Equilibrium modeling was carried out, and the experimental data were expressed in accordance with the Langmuir, Freundlich, Temkin, and Dubinin–Radushkevich isotherms.