Tests were conducted to examine the bond of reinforcement in self-compacting concrete (SCC) produced using recycled coarse aggregate (RCA). The study considered one natural coarse aggregate, two sources of RCA (concrete tested in the laboratory and concrete from demolished old structures), two types of RCA (pre-treated and untreated), three RCA replacement percentages (25%, 50% and 100%) and two types of steel rebar (plain and deformed). The results indicate that the compressive and tensile strengths of the recycled aggregate self-compacting concretes (RA-SCCs) were greatly influenced by the RCA replacement ratio, and the RCA source and type. Using pre-treated RCA, the RCA replacement ratio had little effect on the bond strength of RA-SCC. There was an obvious reduction of the RA-SCC’s bond capacities when the pre-treated RCA was replaced with the low-quality untreated RCA obtained from demolished old structures. Based on regression analysis of the experimental data, an empirical bond stress–slip relationship between RA-SCC and steel rebar was established and it was also proved that the bond strength predictions based on the provisions of existing codes (ACI 318 and GB 50010) were compatible with the experimental results.