Results of an experimental study on the bond performance of deformed steel rebars in concrete made with coarse recycled concrete aggregate (RCA) are presented. The distinctive feature of the study is the new mix proportioning method for RCA concrete that results in the strength to elastic modulus ratio (f′c/Ec) similar to a conventional concrete having the same amount of total mortar and coarse aggregate. In this method, the properties and volume fractions of natural aggregate and residual mortar in RCA are quantitatively included as part of the total aggregate and total mortar content of the RCA concrete. Twelve beam-end bond specimens were prepared and tested according to ASTM A944-99 standard. The test variables comprised mix proportioning method, bar size, and aggregate type. The results showed that the bond strength between the reinforcing steel bars and the RCA concrete proportioned by the new method is comparable to their bond strength with regular concrete but 18% to 33% higher than their strength with RCA concrete proportioned by conventional methods.