In this paper, investigations were undertaken to formulate the properties of fly ash-calcium sulfoaluminate (CSA) cement matrix by blending MSW fly ash with CSA cement. The compressive strength, pore structure, hydration phases, and leaching behavior of Zn and Pb doped MSW fly ash-CSA cement matrices were determined by XRD, MIP, DSC, FTIR, EDX, TCLP leaching test and other experiments. The results showed that the addition of MSW fly ash to form fly ash-CSA cement matrix reduced the compressive strengths of matrices and made the pore distribution of matrices coarser, compared to that of pure CSA cement matrix. However, fly ash-CSA cement matrix could effectively immobilize high concentration of heavy metal such as lead and zinc with much lesser leaching of TCLP. Besides ettringite AFt, Friedel phase was a new hydration phase formed in the matrix. The formation of these hydration phases was responsible for huge reservoir of heavy metal stabilization by chemical fixing. Therefore, it could be postulated that MSW fly ash-CSA cement matrix was a potential new constituent of S/S matrix for high concentration of heavy metals such as Zn and Pb ions.