The paving asphalts have long been recognized to be capable of self-healing. The objective of this study was to evaluate the healing potential of asphalt binders and investigate its relationship with molecular characteristics in terms of composition and structures. Five neat and styrene–butadiene–styrene (SBS) modified asphalt binders were characterized using the recently developed linear amplitude sweep-based healing test. The data were analyzed based on the viscoelastic continuum damage theory to establish healing master curves and determine the healing rate HR. Chemical evaluation methods included saturates, aromatics, resins, and asphaltenes fractionation, gel permeation chromatography, and nuclear magnetic resonance spectroscopy. Results indicated that the presence of more light/low-polarity fractions of saturates and aromatics or higher concentrations of small molecules promoted healing, as these molecules were expected to have higher mobility facilitating molecular diffusion across crack interfaces. Lower percentages of aromatic ring structures and more aliphatic chains corresponded to higher healing rates. The SBS-modified asphalt binders contained higher concentrations of aromatic rings, but still provided comparable healing potential with the neat asphalts.