Sulfate-rich tailings are commonly used as aggregate materials for mine filling, and the sulfate retained within them significantly affects the structural characteristics of cemented paste backfill (CPB). A series of microstructure tests, uniaxial compressive strength (UCS) tests, and acoustic emission (AE) monitoring were carried out on CPB and sulfate tailing-cemented paste backfill (ST-CPB) to investigate the progressive damage pattern and identify the destabilization precursor information of the backfill. The results showed that the UCS of the backfill increased and then decreased with the increase in sulfate content, and 1.5% was the optimal content. The AE counts, energy, amplitude, and peak frequency time series corresponded to each other, exhibited the stage characteristics of a stress curve and were significantly affected by sulfate content. CPB and 0.5% ST-CPB displayed more active AE counts and energy during the initial loading stage, with high amplitude and low-frequency signals. However, the 1.5% ST-CPB exhibited active AE events and medium-high amplitude and medium-low frequency signals only during the plastic yielding and damage stages. 2.5% ST-CPB exhibited more active AE signals during the entire loading process. RA-AF values indicate that CPB and 2.5% ST-CPB reached 93.12 and 96.62% of tensile cracks at final failure, respectively. Meanwhile, the percentages of tensile cracks at the final failure of 0.5 and 1.5% ST-CPB were 76.65 and 76.86%, respectively. The sudden increase in the variance curve and the rapid decrease in the b value of AE in the critical slowdown theory were identified as the precursor characteristics of the backfill instability. This investigation can provide technical and theoretical support for the progressive damage characteristic and stability assessment of ST-CPB.