The low hydration activity and high heavy metal ion content of red mud restrict its application in the field of building materials, and the preparation of good performance and economic and environmental friendly red mud-based cementitious material to realize the large admixture utilization of red mud is a problem to be solved in the green and efficient application of red mud. Red mud-based environmental cementitious material (RFCG) was prepared by activated red mud and fly ash with calcium carbide slag and phosphogypsum. The effects of calcium carbide-phosphogypsum ratio, calcination temperature of red mud, and sealing high-temperature curing time on the strength law of RFCG were investigated, and XRD, SEM-EDS, and ICP-OES were used to explain the strength law of RFCG from the microscopic mechanism and assess the environmental impact of RFCG. The results showed that OH- provided by calcium carbide slag promoted the reaction and generated C-(A)-S-H and a small amount of N-A-S-H gel, which contributed to the strength development of RFCG; AFt generated by SO42- provided by phosphogypsum enhanced the densification of the matrix by filling the microscopic pores to improve the strength, but the excessive AFt led to the development of microcracks in the matrix, which had an impact on the strength development greater. Calcination treatment enhanced the silica-aluminum ion leaching rate of red mud and attenuated the negative effect of organic matter in red mud, resulting in a substantial increase in the strength of RFCG. Conservation at 60 °C for 24 h effectively improved the early strength of RFCG. The prepared RFCG stabilized heavy metal ions, avoided secondary pollution to a certain extent, and could be applied in engineering fields such as pavement subgrade and mine filling.