Asphalt rubber (AR) is a sustainable paving material composed of bitumen and crumb rubber modifier (CRM) recycled from waste tires. The interaction between bitumen and CRM re-distributes the bitumen fractions and creates a multiphase internal structure of AR. Although the superior aging resistance of AR has been acknowledged, the aging mechanism of AR remains unclear due to the limited understanding on the behaviors of different phases of AR during aging. This study aims to investigate the structural and mechanical evolution of AR binder during aging through micromechanical back-calculation and experimental tests. A series of separation methods were used to disintegrate the multiphase system of AR at four aging conditions. The mechanical properties of different phases obtained from frequency sweep tests and their volumetric fractions were used as the input for the micromechanical back-calculation, which yielded accurate prediction for the complex modulus of swelling rubber but failed for that of undissolved rubber, so further chemical characterization was conducted to estimate its mechanical evolution. The results indicated that the aging of AR is a process in which internal multiphase structures changed simultaneously with mechanical properties. All subphases became stiffer but their influences on the overall mechanical property of AR variated after aging.