The effect of concrete grade on the bond between 12 mm diameter deformed steel bars and recycled aggregate concrete (RAC) has been investigated with the help of 45 pullout tests with concentric rebar placement for coarse recycled concrete aggregate (RCA) replacement levels of 25, 50, 75 and 100%. For all the three concrete grades, the measured bond-slip relationships indicate similar mechanisms of bond resistance in the RAC and the natural aggregate (NA) concrete. The most accurate and least conservative predictions of the measured bond strengths were obtained from the local bond-slip model in the fib Model Code for Concrete Structures 2010. Bond strength normalized to fc(3/4) resulted in an improved match with test data and increased with an increase in the RCA replacement levels and decreased with an increase in compressive strength. An attempt to explain this behaviour has been sought in terms of brittleness index, an analogous parameter from rock mechanics. An empirical bond stress versus slip relationship has been proposed for the 12 mm diameter bar and it is conservatively suggested that similar anchorage lengths for this bar in all three concrete grades can be adopted for the RAC and the NA concretes.