The use of calcium aluminate cements to efficiently encapsulate hazardous wastes was reported. Specifically, the quick formation of a matrix of low porosity and high stability was intended. The reaction between phosphate groups and calcium aluminate cement was extremely important in this case. This work presents an acid-base reaction between phosphates present in the sludges from the automotive industry and calcium aluminate cement that yielded very inert and stable monolithic blocks of amorphous calcium phosphate (ACP). Two industrial sludges of different compositions were characterized and loaded in different ratios (from 10 to 50 wt.%). Setting times and compressive strengths were recorded to establish the feasibility of this method to achieve a good handling and a safe landfilling of these samples. Short solidification periods were found and leaching tests showed an excellent retention for toxic metals such as Zn, Ni, Cu, Cr and Mn and also for organic matter. Retentions over 99.9% for Zn and Mn were observed even for loadings as high as 50 wt.% of the wastes. The formation of ACP phase of low porosity and high stability accounted for the effective immobilization of the hazardous components of the wastes, as confirmed by X-ray diffraction and SEM-EDAX studies. Comparison with the performance of pure sodium hexametaphosphate-CAC mortars bearing toxic metals solutions was sometimes reported.