<p>Desulfurization is crucial for activating crumb rubber (CR) to improve the compatibility of rubberized asphalt, and pretreatment with heavy bio-oil has emerged as a synergistic approach to facilitate this process. However, its quantitative effects on mechanical properties, particularly intermediate-temperature cracking resistance, have yet to be thoroughly evaluated. In this study, crumb rubber pretreated with heavy bio-oil was subjected to distinct processing methods to achieve a wide spectrum of desulfurization degrees, as indicated by a sol fraction ranging from 5.33 to 17.37% and a decrosslinking degree ranging from 34.23 to 76.34%. The structural evolution of the rubber network was quantified, and its correlation with the rheological and cracking performance of the modified binder was evaluated. Results indicated that desulfurization degree was effectively reduced by bio-oil pretreatment and can be primarily characterized by the sol fraction, given its established strong linear correlation (semi-logarithmic) with crosslink density and decrosslinking degree. Grey relational analysis demonstrated that decrosslinking degree and sol fraction content were strong indicators affecting binder performance. Notably, an excessive desulfurization degree (sol fraction &gt; 7.2%) compromised the integrity of the rubber network, reducing the fracture energy density by 6.2 MPa for each unit increase in sol fraction, and concomitantly deteriorating the cracking resistance. Considering the technical specifications for workability and storage stability, optimal desulfurization range was identified as 41.2–49.6% for decrosslinking degree and 6.2–7.2% for sol fraction. It can be concluded there was an optimal range of desulfurization degree for crumb rubber modified asphalt binders based on both rheological and mechanical properties.</p>