Abstract: To investigate the long-term service performance of cemented graphite tailings backfill materials (GCTB) incorporating recycled fine powder in complex mining environments, this study examined the variations in mass (MS), unconfined compressive strength (UCS), and relative dynamic modulus (RDM) of GCTB samples under different immersion temperatures, salt solution types, and numbers of wet-dry cycles. The deterioration mechanisms were revealed using SEM-EDS and XRD. The results indicated that the MS, UCS, and RDM of the GCTB initially increased and then decreased with increasing numbers of wet-dry cycles. In the composite salt solution of NaCl and Na₂SO₄, SO₄²⁻ preferentially reacted with the Al phase in the system during the early cycles due to its lower thermodynamic equilibrium constant, leading to the formation of ettringite (AFt), which effectively filled the internal pores and enhanced the macroscopic properties. During the later cycles, Cl⁻ accumulated inside the samples owing to its higher penetration rate, promoting the formation of Friedel’s salt through ionic equilibrium effects, thereby inhibiting AFt formation. Meanwhile, excess SO₄²⁻ was converted into gypsum (CaSO₄·2H₂O). The continuous accumulation of expansive deterioration products, including Friedel’s salt, gypsum, and AFt, collectively induced expansive damage, resulting in internal cracking and macroscopic performance degradation of the GCTB. Elevated temperatures promoted ion migration and reaction rates, which shifted the peaks in mass, UCS, and RDM to earlier at 10 cycles while also accelerating damage development and further reducing durability.