Abstract: Coal-based green filling materials exhibit component diversity and multi-dimensional performance. Considering the entire solidification process of the backfill and scientifically selecting a multi-component formulation is the primary concern for ensuring mine backfill quality. Accordingly, a Box-Behnken design (BBD) was first employed, with fly ash content (20%‒60%), slurry concentration (82%–86%), and gangue-to-binder ratio (3–7) as independent variables to construct response-surface models for the backfill’s overall solidification performance (bleeding rate, setting time, and 28 d uniaxial compressive strength). Analysis of variance indicates that all regression coefficients in the models are statistically significant, prediction errors remain within 5%, and the models demonstrate very high fitting accuracy and reliable predictive capability. Fly ash content significantly influences bleeding rate and setting time; increasing fly ash improves slurry stability but delays setting. Slurry concentration is most sensitive to strength enhancement, with higher concentrations markedly boosting hydration efficiency. The gangue-to-binder ratio shows significant interactions with both concentration and fly ash content regarding strength and setting behavior. Next, the non-dominated sorting genetic algorithm NSGA-II was introduced for multi-objective optimization, yielding over 100 Pareto-optimal formulations. By treating suitable setting time and controlled bleeding rate as basic constraints, and maximizing backfill strength and coal-based solid-waste utilization as objectives, three representative formulations meeting all constraints were selected, validating the practicality of the NSGA-II approach for filling-material design. This BBD-NSGA-II–based method realizes scientific decision-making for multi-component coal-based green filling materials and can serve as a reference for similar formulation optimization.