Pavements are constantly subjected to oxidation and aging during their performance life, causing an increase in stiffness and brittleness and their lower ability to withstand stresses. This is even more pernicious when using reclaimed asphalt pavement (RAP) which cannot be used as it is and needs to be modified with rejuvenators. Up to now, the rejuvenating effect has been evaluated in terms of the improvement of rheological properties whereas the rejuvenation mechanism at micro-scale remains unclear. In this work, RAP with three different bio-based rejuvenators (a natural seed oil, a cashew-nut shell-based oil and a tall based oil) have been analysed by using dynamic shear rheometer (DSR) in combination with atomic force microscopy (AFM). Rheological tests showed how rejuvenators may restore the mechanical properties of RAP binder. On top of, AFM has been used to measure the mechanical properties at the sample's surface such as the Young's modulus. Consequently, quantitative nano-mechanical surface maps have been created and the effect of rejuvenators in restoring the elastic moduli at the RAP's surface has been demonstrated. Furthermore, samples were analyzed after standard aging procedures (RTFOT and PAV) and rejuvenators' effect have been studied. The addition of rejuvenators decreased the elastic moduli of the RAP binder at the sample's surface and the bulk by decreasing the complex moduli. However, aging had a consequence on all binders' surface and this effect was rejuvenators' dependent.