Municipal solid waste incineration (MSWI) fly ash is a typical hazardous waste worldwide. In this study, an innovative magnesium oxysulfate cement (MOSC) binder was designed for stabilization/solidification (S/S) of MSWI fly ash, focusing on the interactions between MOSC binder and typical metallic cations (Pb2+)/oxyanions (AsO33-). Experimental results showed that Pb and As slightly inhibited the reaction of high-sulfate 5MS system but significantly suppressed the reaction process of low-sulfate 10MS system. The 5MS binder system exhibited excellent immobilization efficiencies (99.8%) for both Pb and As. The extended X-ray absorption fine structure spectra suggested that Pb2+ coordinated with SO42-/OH- in the MOSC system and substituted Mg2+ ion sites in the internal structure of 5Mg(OH)2·MgSO4.7H2O (5−1−7) phase. In contrast, the AsO33- substituted SO42- sites with the formation of inner-sphere complexes with Mg2+ in the large interlayer space of the 5–1–7 structure. Subsequent MSWI fly ash S/S experiments showed that a small amount of reactive Si in MSWI fly ash interfered with the MOSC reaction and adversely influenced the immobilization efficiencies of Pb, As, and other elements. Through the use of 33 wt% tailored MOSC binder for MSWI fly ash treatment, a satisfying S/S performance could be achieved.