The mechanical properties of Recycled Aggregate Concrete (RAC) with different mixing approaches were comparatively investigated. Based on the experiments on the Interfacial Transition Zone (ITZ) of RAC by nanoindentation technique and scanning electron microscopy, the results indicate that, for the new ITZ with Normal Mixing Approach (NMA), the elastic modulus distribution appears to decrease significantly from the old paste matrix surface, while for the new ITZ with Two-Stage Mixing Approach (TSMA), there is no obvious trend indicating that the elastic modulus increases or decreases with the increase of distance. For the old ITZ, the elastic modulus increases as the distance increases from original aggregate surface. The TSMA can improve the microstructures of the new ITZ by reducing the volume fraction of voids and calcium hydroxide. Correlating the nanomechanical properties of ITZ and microstructure with the compressive strength of RAC, it can be concluded that TSMA can enhance the mechanical properties of RAC by improving the mechanical properties and microstructure of the new ITZ.