The present study aimed to investigate the durability and microstructure evolution of road base materials (RBM) prepared from red mud and flue gas desulfurization fly ash. The durability testing showed that the strength of RBM with the blast face slag addition of 1wt%, 3wt% and 5wt% reached 3.81, 4.87, and 5.84 MPa after 5 freezing–thawing (F–T) cycles and reached 5.21, 5.75, and 6.98 MPa after 20 weting–drying (W–D) cycles, respectively. The results also indicated that hydration products were continuously formed even during W–D and F–T exposures, resulting in an increase of the strength and durability of RBM. The observed increase of macropores (＞1 μm) after F–T and W–D exposures suggested that the mechanism of RBM deterioration is pore enlargement due to cracks that develop inside their matrix. Moreover, the F–T exposure showed a greater negative effect on the durability of RBM compared to the W–D exposure. The leaching tests showed that sodium and heavy metals were solidified below the minimum requirement, which indicates that these wastes are suitable for use as a natural material replacement in road base construction.