Abstract: The safety and efficiency of mining operations depend on the strength of backfill, and cementitious materials play a key role in achieving high-strength backfill. The stockpiling of fly ash (FA) and desulfurization gypsum (DG) poses serious environmental pollution risks and urgently requires effective treatment to achieve sustainable resource utilization. This study develops a cementitious composite system that integrates FA, DG, and cement. It systematically investigates the effects of DG mass fraction, FA mass fraction and water-to-binder mass ratio (w/b) on the properties of cementitious materials to optimize the mix ratio of backfill slurry binders and enhance comprehensive utilization of solid waste. In this study, a three-factor, three-level orthogonal experiment was designed using the response surface methodology (RSM) to prepare cementitious paste test blocks and to test their compressive strength at 3, 7, and 28 d (hereafter denoted as 3 d, 7 d, and 28 d). Based on the experimental results, range analysis was employed to determine the ranking of influencing factors and to identify the optimal mix ratios for each curing age. Additionally, overall efficacy coefficient analysis was used to optimize the mix design by comprehensively considering the strengths across multiple curing ages. A multivariate nonlinear regression analysis was 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 was established through the assignment of subjective weight coefficients. Finally, X-ray diffraction (XRD) and scanning electron microscopy with energy-dispersive spectroscopy (SEM–EDS) analyses were conducted to investigate the microstructural mechanisms underlying the consolidation of cementitious materials. 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- (3 d), medium- (7 d), and late-stage (28 d) strengths are mass fraction of DG, mass fraction of FA, and water-to-binder mass ratio, respectively. Range analysis reveals the optimal mix proportions as 10% DG, 50% FA, and w/b=0.32 for 3 d strength; 10% DG, 67% FA, and w/b=0.36 for 7 d strength; and 20% DG, 50% FA, and w/b=0.32 for 28 d strength. Considering all three ages, the water-to-binder mass ratio is the most influential factor, with the optimal composite mix determined to be 15% DG, 50% FA, and a w/b of 0.32. The regression coefficients (R²) of the multivariate nonlinear quadratic response surface models for each age are close to 1, indicating excellent fitting accuracy. The total objective function derived from the regression models and subjective weights yields a maximum value of 48.3 MPa and a minimum value of 21.2 MPa. Strength at all ages is most sensitive to the interaction between mass fraction of DG and FA. XRD and SEM analyses confirm that the primary hydration products of the FA–cement–DG system are C–S–H gel, Ca(OH)₂, and ettringite (AFt, calcium aluminate trisulfate hydrate). With increasing curing age, enhanced hydration and increased product formation fill internal pores, leading to gradual strength development. Excessive mass fraction of FA reduces strength due to the incomplete participation of FA in hydration reactions. This research provides theoretical guidance for optimizing the mix design of FA-based cementitious materials in mine backfill applications, particularly regarding the rational allocation of DG mass fraction, FA mass fraction, and water-to-binder mass ratio to balance early and long-term strength requirements.