In this paper, the use of recycled aggregate concrete (RAC) for the upper slabs in steel-concrete composite beams is proposed. Perfobond rib connector (PBL), a relatively new type of shear connectors, has been widely used to ensure composite action between the steel and concrete elements in composite beams. For the past decades, several studies on assessing the performance of PBLs have been conducted, but very few focused on the PBLs that are embedded in RAC slabs. This paper presents results of an experimental and numerical simulation study that focused on characterizing the behavior of PBL fabricated using RAC. In the experimental program, a total of six standard push-out specimens, divided into three groups, were fabricated and loaded to failure. Test results indicated that the ductility of the PBLs using RAC materials decreased as the perforated steel plate thickness decreased, while the PBL ultimate strength increased by 4.3% and 12.8% for steel plate thicknesses of 10.0 mm and 12.0 mm, respectively, as compared to specimens with 8.0 mm steel plate thickness. Finite element (FE) models for PBLs embedded in RAC were developed, and numerical results were validated by corresponding experimental results. An extensive parametric numerical analysis was conducted to assess the effects of different parameters such as transverse steel rebar diameter and perforated steel plate strength and thickness on the performance of such connectors. Numerical simulation results showed that the PBL ultimate strength obtained based on the perforated plate fracture failure mode increases linearly as the steel rebar diameter increases. Also, numerical results indicated that as steel plate strength and thickness increase, failure mode changes from steel plate fracture to rupture of reinforced concrete dowels. Furthermore, existing published analytical formulas for predicting behavior of PBLs were assessed via a comparison with experimental and numerical results developed in this study. The outcomes of this study contribute in providing fundamental knowledge in a new sustainable application of PBL in steel-concrete composite beams with RAC slabs.