Abstract: To address the issue of oxygen hazards caused by air leakage in abandoned coal mine areas, this study focuses on implementing carbon reduction and solid waste utilization strategies. It involves the selection of red mud, cement, and metakaolin as primary materials to prepare a new multi-component cementitious material (R−M−S−C−D) and conduct research on its sealing performance. Using water-to-cement ratio, the proportion of red mud to metakaolin, the amount of silica fume, and the amount of desulfurization gypsum as variables, a four-factor, four-level orthogonal experiment was designed. The flowability of the cementitious material was tested, and bending strength, compressive strength, pore structure characteristics, product composition, functional groups, and morphological features were analyzed microscopically. The experimental results indicate that, under the influence of a water-reducing agent, the optimal mix ratio for the new multi-component cementitious material is a water-to-cement ratio of 0.5, with red mud at 18%, metakaolin at 18%, desulfurization gypsum at 6%, silica fume at 8%, and cement at 50%. At this ratio, the performance of the new multi-component cementitious material is optimal, achieving a bending strength of 7.53 MPa, a compressive strength of 28.87 MPa, and a porosity of 17.89%. XRD analysis reveals that the hydration products of the multi-component cementitious material include Ca(OH)₂, CaCO₃, and calcium silicate hydrate gel (C−S−H), among other gels and crystals. FTIR analysis indicates an increase in Si—O and Al—O bonds within the material. TG analysis shows significant mass loss of bound water in the hydration products between 30°C and 200°C, indicating the formation of a large amount of gel and crystals in R−M−S−C−D. SEM scanning observed a substantial presence of network-like or clustered gels and crystals such as ettringite. Under the synergistic activation of alkalis and sulfates, the cementitious material reacts to produce calcium silicate hydrate gel (C−S−H), calcium aluminosilicate hydrate gel (C−A−S−H), ettringite, and other products, which provide excellent structural support and pore-filling effects, while optimizing mechanical properties and pore structure. This study demonstrates that the new solid waste system based on red mud and cement has promising applications for sealing air leaks in coal mines.