Due to the depletion of natural aggregates and raw materials for contemporary construction, the construction and demolition waste existing in old concrete structures is an imperative problem. Cutting down on exploiting natural aggregates and reusing construction and demolition waste in the concrete industry are solutions to this problem. This paper investigated the replacement of natural coarse aggregate (NCA) with recycled concrete aggregates (RCA) with different ratios (0%, 50%, 75%, and 100%) in producing self-compacting concrete (SCC). Different components of supplementary cementitious materials (SCMs), such as nano-silica (NS), fly ash (FA), and metakaolin (MK), as well as PVA fibers, were incorporated into the SCC mixtures. The fresh properties (slump flow, V-funnel, and L-box test) and hardened properties (compressive strength, splitting tensile strength, and flexural strength), as well as the flexural behavior of SCC beams (load-carrying capacity, crack pattern, midspan deflection, and flexural stiffness), were studied for all SCC mixes. The results of fresh and hardened concrete confirmed that it is possible to produce SCC with a 100% replacement of RCA with minimal effects on the concrete properties. The mixture of SCC with 100% RCA replacement, 20% MK, and 22% FA was the optimum mixture with acceptable fresh properties that complied with the EFNARC specifications. For 100% RCA replacement, the compressive strength was reduced by 8.20%, and the ultimate load and flexural stiffness increased by 3.20 and 16.25%, respectively, compared with the control mixture.