This article presents the results of a research developing high performance cement mortars with the addition of municipal solid waste incineration fly ash (MSWIFA) stabilized as insoluble carbonates. The encapsulation of hazardous wastes in mortar matrixes has also been achieved. The ashes present high concentrations of chlorides, Zn and Pb. A stabilization process with NaHCO3 has been developed reducing 99% the content of chlorides. Developed mortars replace 10% per weight of the aggregates by treated MSWIFA. Physical/mechanical properties of these mortars have been studied. Presence of Zn, Pb, Cu and Cd has been also analyzed confirming that leaching of these heavy metal ions is mitigated. Conclusions prove better behavior of CAC and CSA mortars than those of CEM-I and CEM-II cement. Results are remarkable for the CAC mortars, improving reference strengths in more than 25%, which make them a fast-curing product suitable for the repair of structures or industrial pavements.