In this work, the relation between the self-healing ability of crumb-rubber-modified asphalt (CRMA) and the formation of an internal three-dimensional (3D) network structure was studied. This was done through the investigation of the effect of change in binder fractions (asphaltenes, saturates, naphthene aromatic, and polar aromatics; resins) on the self-healing ability of CRMA as a result of modifying the CRMA's internal network structure. The presence of 3D network structures in CRMA enhances the self-healing capabilities of the binder, thus leading to better in-service pavement performance. Interrupted shear flow tests were carried out to determine the existence of 3D network structures in CRMA. Interrupted shear flow tests were utilized to investigate the self-healing ability of the materials by imposing a predefined shear rate and then measuring the resulting shear stress. It was found that the asphalt type and fractions, crumb-rubber (CR) type and percentage, and the interaction conditions between them affect the development of the 3D network structures in CRMA. Lower PG asphalts with abundant saturates and naphthene aromatics produced the maximum amount of shear stress overshoot, indicating the highest occurrence of 3D network structures. Cryogenic-processed mixed-source CR had better performance in terms of the network structure formation over the ambient-processed CR. A 10% CR percentage had the best network structure formation over the 15% or 20%. A combination of a moderate interaction temperature (190°C) and high interaction speed (50Hz) produced a well-developed 3D network structure in the CRMA.