Thirty one push-out tests were carried out in order to investigate the bond behavior between shape steel, steel tube (named steels) and recycled aggregate concrete (RAC), including 11 steel reinforced recycled aggregate concrete (SRRAC) columns, 10 recycled aggregate concrete-filled circular steel tube (RACFCST) columns and 10 recycled aggregate concrete-filled square steel tube (RACFSST) columns. Eleven recycled coarse aggregate (RCA) replacement ratios (i.e., 0%, 10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, 90% and 100%) were considered for SRRAC specimens, while five RCA replacement ratios (i.e., 0%, 25%, 50%, 75% and 100%), concrete type and length-diameter ratio for recycled aggregate concrete-filled steel tube (RACFST) specimens were designed in this paper. Based on the test results, the influences of all variable parameters on the bond strength between steels and RAC were investigated. It was found that the load-slip curves at the loading end appeared the initial slip earlier than the curves at the free end. In addition, eight practical bond strength models were applied to make checking computations for all the specimens. The theoretical analytical model for interfacial bond shear transmission length in each type of steel-RAC composite columns was established through the mechanical derivation, which can be used to design and evaluate the performance of anchorage zones in steel-RAC composite structures.