Abstract: The safety and efficiency of mining operations depend on the strength of the backfill, and cementitious materials are the key to obtaining high-strength backfill. The stockpiling of fly ash and desulfurization gypsum poses serious environmental pollution risks and urgently requires effective treatment to achieve sustainable resource utilization. This study develops a cementitious composite system by integrating fly ash, desulfurization gypsum, and cement. It systematically investigates how the desulfurization gypsum content, fly ash ratio, and water-binder (w/b) ratio influence the properties of cementitious materials, aiming to optimize the mix ratio of backfill slurry binders and enhance the comprehensive utilization of solid waste. In this study, a three-factor, three-level orthogonal experiment is designed using the response surface methodology (RSM) to prepare cementitious paste test blocks and test their compressive strengths at 3, 7, and 28 days. Based on the experimental results, range analysis is employed to determine the ranking of influencing factors and identify optimal mix ratios for each curing age. Additionally, the overall efficacy coefficient analysis is used to optimize the mix design by considering the strengths across multiple curing ages comprehensively. A multivariate nonlinear regression analysis is conducted to develop regression models with strength as the response variable, revealing the effects of individual factors and their interactions on strength at different curing ages. Meanwhile, a weighted objective function incorporating all three curing ages is established through subjective weight coefficient assignment. Finally, XRD and SEM analyses are performed to investigate the microstructural mechanisms underlying the cementitious material consolidation. The research results indicate that the compressive strengths of all specimen groups meet the engineering application requirements for cementitious materials. The primary factors influencing early (3d), medium (7d), and late (28d)-stage strengths are desulfurization gypsum content, fly ash ratio, and water-binder ratio, respectively. Range analysis reveals the optimal mix proportions as 10% gypsum, 50% fly ash, and w/b = 0.32 for 3-day strength, 10% gypsum, 67% fly ash, and w/b = 0.36 for 7-day strength, and 20% gypsum, 50% fly ash, and w/b = 0.32 for 28-day strength. Considering all three ages, water-binder ratio is the most influential factor, with the optimal composite mix determined as 20% gypsum, 50% fly ash, and w/b = 0.32. The regression coefficients (R2) of the multivariate nonlinear quadratic response surface models for each age approach 1, indicating excellent fitting accuracy. The total objective function derived from the regression models and subjective weights yields a maximum value of 48.29 MPa and a minimum value of 21.20 MPa. Strength at all ages is most sensitive to the interaction between desulfurization gypsum content and fly ash ratio. XRD and SEM analyses confirm that the primary hydration products of the fly ash-cement-desulfurization gypsum system are C-S-H gel, Ca(OH)2, and ettringite (AFt). With increasing curing age, enhanced hydration and increased product formation fill internal pores, leading to gradual strength development. Excessive fly ash content reduces strength due to incomplete participation of fly ash in hydration reactions. This research provides theoretical guidance for optimizing the mix design of fly ash-based cementitious materials in mine backfill applications, particularly regarding the rational allocation of desulfurization gypsum content, fly ash ratio, and water-binder ratio to balance early and long-term strength requirements.