This paper aims to explore the potential use of flue gas desulfurisation gypsum (FGDG) and phosphogypsum (PG) into cemented paste backfill (CPB). The mechanical strength of CPB and the binder paste properties (i.e., hydration heat, hydration evolution, acid erosion resistance, and leachability) were investigated experimentally. The results revealed that the addition of FGDG and PG significantly improved the mechanical performance of CPB by lowering the porosity and increasing the formation of ettringite (AFt) in the early stages. The normalized hydration heat of blended binders was decreased significantly due to replacement of cement with mineral admixtures (i.e., fly ash [FA], FGDG, PG, and quicklime). Dissolved FA decreased the Ca/Si ratio of blended binders, promoted the incorporation of aluminium into the C–S–H gel, and increased the acid erosion resistance. Moreover, the addition of quicklime led to the generation of extra portlandite, which improved the acid erosion resistance. Heavy metals were immobilised by hydration products, and the addition of quicklime further enhanced the stabilisation. The novel binders (SPC + FA + FGDG/PG + quciklime) show prospective application in CPB technology.