The combined use of recycled concrete aggregate (RCA) and glass fiber reinforced polymer (GFRP) reinforcement in reinforced concrete (RC) structures is deemed plausible to achieve sustainable construction. This paper aims to examine the effect of such a combination (RCA + GFRP reinforcement) on the shear behavior of RC beams. Six medium-scale RC beams (150 × 260 × 2200 mm) critical in shear were tested under three-point loading until failure. The test variables were the aggregate type (natural/recycled) and the shear reinforcement (steel/GFRP/none). The failure modes, cracking patterns, load-carrying capacities, deformational and strain characteristics were analyzed and compared among the tested specimens. It was found that using 100% RCA in the concrete mix reduced the shear strength of RC beams (by 12% on average). Minor effects were observed on the shear strength of the beam specimens (∼2%) with altering the transverse reinforcement (GFRP versus steel). Theoretical load-carrying capacities of the tested beams were obtained as per contemporary design guides and compared with the experimental results.