The removal of fluoride from environmental surface water and groundwater is an important environmental issue in Tunisia. Notably, Tunisia also faces a shortfall in reservoir capacity due to the buildup of sediment containing calcium carbonate. Dicalcium phosphate dihydrate (DCPD, CaHPO4·2H2O) reacts effectively with fluoride to form stable fluorapatite (FAp, Ca10(PO4)6F2), and the addition of calcium carbonate (CaCO3) effectively inhibits the release of phosphate generated during this reaction. In this study, we tested the potential for fluoride removal using a mixture of DCPD and Tunisian reservoir sediment. The release of phosphate from the reaction of DCPD with fluoride was successfully inhibited using the sediment. The application of the DCPD–sediment mixture led to a high rate of fluoride removal (15–19 mg/g), such that the resulting water met the World Health Organization (WHO) recommended limit for fluoride in water (1.5 mg/L). This removal rate is five to ten times those achieved with conventional fluoride adsorbents such as bone char. Based on these results, the utilization of Tunisian reservoir sediment seems to be an effective solution for removing fluoride from aqueous environments.