Polyphosphate-modified calcium aluminate cement matrices were prepared by using aqueous solutions polluted with toxic metals as mixing water to obtain waste-containing solid blocks with improved management and disposal. Synthetically contaminated waters containing either Pb or Cu or Zn were incorporated into phosphoaluminate cement mortars and the effects of the metal’s presence on setting time and mechanical performance were assessed. Sorption and leaching tests were also executed and both retention and release patterns were investigated. For all three metals, high uptake capacities as well as percentages of retention larger than 99.9% were measured. Both Pb and Cu were seen to be largely compatible with this cementitious matrix, rendering the obtained blocks suitable for landfilling or for building purposes. However, Zn spoilt the compressive strength values because of its reaction with hydrogen phosphate anions, hindering the development of the binding matrix.