Treatment by accelerated carbonation has been widely studied to enhance the quality of recycled concrete aggregates (RCA) and hence the performance of new concrete produced with the RCA. This is often ascribed to the densification of RCA. This study investigated the influence of carbonation treatment of modeled RCA on the interface between the carbonated RCA and new cement mortar/paste using frictional (shear) and tensile bond tests, microhardness, X-ray diffraction (XRD), thermal analysis (TGA), and scanning electron microscope (SEM). It was found that carbonation treatment resulted in massive calcite precipitating on the surface of RCA, which further reacted with the aluminate species of the new cement to form the monocarbonate (Mc), and served as nucleation sites for the grow of C-S-H on the surface of RCA. These led to local densification around the surface of the carbonated RCA, resulting in a slight reduction of the porosity at the innermost part of ITZ and improved microhardness of ITZ. Moreover, the chemical bonds provided a superior adhesion of the carbonated RCA with the new cement pastes. This improved the bond strengths between the carbonated RCA and the new cement mortar.