Abstract: To address the challenges of coal-based solid waste generated from coal gangue power generation, surface subsidence induced by coal mining, and associated geological hazards in the Qinyuan Mining Area of Shanxi Province, this study takes the Qinyuan Xinyuan Coal Mine as a case study. Considering the distribution of coal seams pressed under buildings, railways, and water bodies, a novel composite cementitious material was using coal-based solid wastes—fly ash, desulfurization gypsum, and carbide slag—as raw materials, with cement and water as auxiliary components. Using the single-variable method, the effects of different raw material ratios on slurry fluidity, bleeding rate, compressive strength of hardened specimens, and chemically bound water content were systematically investigated. Based the analysis of the experimental results, the optimal proportion of the composite cementitious material was determined. X-ray diffraction (XRD) and scanning electron microscopy (SEM) were used to analyze the crystalline phase composition and microstructure of the hydration products, revealing the synergistic hydration mechanism of the multi-component solid wastes. The results show that the optimal proportion is as follows: mass ratio of fly ash to desulfurization gypsum of 70:30, carbide slag content of 20%, cement content of 10%, and water-to-binder ratio of 0.65. Under this proportion, the composite cementitious material exhibits excellent performance, with fluidity ranging from 180 mm to 220 mm, a bleeding rate of less than 5% within 6 hours, and a 28 d compressive strength of 17.69 MPa. Microscopic analysis indicates that carbide slag increases the alkalinity of the system, effectively activating the pozzolanic activity of fly ash, while desulfurization gypsum promotes the formation of ettringite crystals, which interweave with hydrated gel to form a dense structure, thereby enhancing material strength. Field test results demonstrate that the strength of the paste backfill material with this proportion meets the requirements for ground deformation and subsidence control.