Against the backdrop of carbon neutrality, the synergistic disposal of coal mine solid wastes and municipal solid waste incineration (MSWI) fly ash is crucial for realizing clean utilization of hydrocarbon resources and solid waste recycling. However, cementitious materials, core for mine backfilling and surface construction, lack sufficient mechanical properties; MSWI fly ash poses environmental risks due to heavy metals; and carbon nanotubes (CNTs) easily agglomerate, hindering their reinforcing effects. To address these three core issues, this study explores the coupling mechanism between solid waste resource utilization and cement performance improvement via FA-CNTs synergistic modification, aiming to support high-value solid waste utilization in mining engineering. Adopting the technical route of “material characterization-dispersion optimization-performance testing-mechanism revelation”, the research analyzed fly ash’s microstructure and composition, optimized CNTs dispersion, prepared simulated cement pore solutions with varying fly ash replacement rates, and tested modified cement samples’ mechanical properties, verifying mechanisms via microscopic analysis. Results confirmed a synergistic reinforcing effect between fly ash and CNTs, with fly ash replacement rate showing a “first increase then decrease” correlation with cement strength. The interaction between the two components significantly affected strength variation, improved CNTs dispersion reduced cement matrix porosity, and modified fly ash achieved effective heavy metal solidification. Microscopically, CNTs inhibited microcrack propagation while fly ash filled pores via C-S-H gel, synergistically optimizing the cement system. This study achieves the triple goals of solid waste harmlessness, material high performance, and efficient carbon resource utilization.