The purpose of this study was to investigate the influence that replacing natural coarse aggregate with recycled concrete aggregate (RCA) has on concrete bond strength with reinforcing steel. Two sources of RCA were used along with one natural aggregate source. Numerous aggregate properties were measured for all aggregate sources. Two types of concrete mixture proportions were developed replacing 100% of the natural aggregate with RCA. The first type maintained the same water–cement ratios while the second type was designed to achieve the same compressive strengths. Beam-end specimens were tested to determine the relative bond strength of RCA and natural aggregate concrete. On average, natural aggregate concrete specimens had bond strengths that were 9 to 19% higher than the equivalent RCA specimens. Bond strength and the aggregate crushing value seemed to correlate well for all concrete types.