Red mud is a kind of solid waste in the production process of the aluminum industry. The long-term stockpiling of red mud not only occupies a large amount of land but also causes environmental pollution. In order to improve the strength, reduce the alkalinity and toxicity of red mud, and study its durability under freeze-thaw cycles, CGFPA binders, whose components were calcium carbide residue, ground granulated blast furnace slag, fly ash, phosphogypsum, and graphene, were adopted to solidify/stabilize red mud in this paper. The effects and the mechanism of freeze-thaw cycling on the unconfined compressive strength, pH value, and toxic leaching of the solidified/stabilized red mud was investigated. The micro-mechanism was analyzed by XRD, SEM-EDS, and FT-IR. The results of the study showed that the mass, unconfined compressive strength, and pH of the solidified/stabilized red mud decreased gradually with an increase in the number of freeze-thaw cycles, while the leaching concentration of pollutants increased gradually. The rate of loss of unconfined compressive strength satisfies an exponential function with the number of cycles, and the logarithm of pollutant concentration satisfies a linear relationship with the number of cycles. The cumulative loss of mass was 6.7%, 5.4%, 3.6%, and 3.3%, and the cumulative loss of unconfined compressive strength was 50.6%, 47.5%, 32.2%, and 25.3%, and the pH value was reduced to 9.42, 9.54, 9.80, and 9.92, respectively, after 10 freeze-thaw cycles at binder mixing ratios of 15%, 20%, 25%, and 30%, while the leaching concentrations of Cu, Zn, Cr, Ni, As, Pb, and Cd increased from 7.4 μg/L, 87.2 μg/L, 5.2 μg/L, 7.0 μg/L, 6.9 μg/L, 3.7 μg/L, and 0.7 μg/L to 17.5 μg/L, 123.5 μg/L, 10.2 μg/L, 15.7 μg/L, 11.4 μg/L, 5.6 μg/L, and 4.9 μg/L, respectively, under the condition of a 30% incorporation ratio. The gelling products generated by the hydration reaction of the binders were mainly C-S-H, C-A-S-H, C-A-H, AFm, etc. Under the action of freeze-thaw cycles, the lattice-like structure of the solidified/stabilized red mud was damaged, resulting in a decrease in its unconfined compressive strength and an increase in pollutant leaching concentration. The research results can provide a theoretical basis for the use of red mud in permafrost regions.