The use of byproducts as supplementary cementitious materials (SCMs) and recycled coarse aggregates (RCAs) can contribute to the production of more sustainable self-compacting concrete (SCC) while modifying the durability properties of these mixtures. Thus, this study addresses the combined use of concrete waste (CW) as RCA and residue of masonry (RM) as SCM, the CW and RM obtained from construction and demolition waste, to generate SCC mixtures and to evaluate the performance of these mixtures under sulfate attack (5% Na2SO4 and 5% MgSO4 solutions). In detail, a reference SCC (M1) and three SCCs with 25% of RM and different level RCAs (0%, 50%, and 100% replacement by volume) were cast. The hardened properties of the SCC mixtures were assessed in terms of compressive strength and sulfate attack. The results showed that the SCC mixtures with RM and RCA, cured in water, exhibited lower compressive strength results in all the evaluated ages compared with M1 (reference mixture, without RM and RCA). However, the SCC mixture with RM presented the maximum compression strength result among the different mixtures at 180 and 360 days. When mixtures were exposed to sulfate solutions, the SCC mixture with RM showed the best performance, and even the SCC mixtures with RM and RCA exhibited lower linear expansion and loss of compressive strength when compared with M1. The presence and severity of the sulfate attack were assessed via X-ray diffraction and scanning electron micrograph, which confirmed the presence of ettringite and gypsum in all the exposed SCC mixtures in the Na2SO4 and MgSO4 solutions.