A novel multiple solid waste-based cementitious material (MSWCM) was developed to immobilize municipal solid waste incineration (MSWI) fly ash. The compressive strength of MSWCM with different ratios of MSWI fly ash reached the standard requirements after curing for 28 days. X-ray powder diffraction (XRD) in combination with the Rietveld method was employed to investigate the content and phase transformation of hydration products. The main hydration products of pure MSWCM paste were C-S-H, hydroxyapatite, ettringite and C-A-S-H. With increases in curing time, the content of ettringite and C-A-S-H increased significantly. The main hydration products of MSWCM paste with MSWI fly ash were C-S-H and Friedel’s salt. The contents increased markedly with increased curing time from 21.8% to 28.0% and from 8.53% to 16.7%, respectively. Additionally, a small amount of PbHPO4 (0.51−0.96%) and lead phosphate Pb3(PO4)2 (0.14−0.51%) were detected, indicating that phosphate had an effective curing effect on lead ions. The results showed that most of the hydration reactions had started at the initial stage of curing and reacted quickly to form a large number of hydration products. The quantitative analyses of hydration products provide essential information for understanding the immobilization mechanism of MSWI fly ash in MSWCM paste.