Countermeasures to the aging of bituminous asphalt binders is a highly important topic for service-life extension of asphalt in the field and for recycling old pavements into new structures with similar functional requirements as the original structure. Countermeasures are usually achieved by applying additives that restore the adhesive and mechanical properties of the original bituminous binder. The additives are commonly termed (asphalt) rejuvenators. This study examined the performance of two very distinct rejuvenating agents. The effectiveness of rejuvenators is usually measured by comparing the penetration and softening point of the rejuvenator-aged bitumen blend with reference values of the virgin binder. The study used a dynamic shear rheometer to evaluate the rejuvenating capabilities of the two additives. The microstructures of the virgin binder and the rejuvenated blends were obtained by atomic force microscopy. Subsequently, the rheological results were related to the microstructure morphologies. From the rheological experiments, both rejuvenators exhibited the desired softening and property-restoring performance. However, there was a strong difference in the amount of rejuvenator needed to achieve complete rejuvenation. By correlating rheology to the microstructural observations, the effects of the rejuvenators were found to be distinct at microscopic length scales: rejuvenation was achieved by distinct chemophysical mechanisms. One of the rejuvenators restored the virgin microstructure, whereas the other rejuvenator generated a new morphology. Thus, the study demonstrated that by combining rheological and microstructural techniques, the mechanism and performance of rejuvenation can be understood. This finding may help guide future designs and optimization of asphalt-rejuvenating agents.