Incorporating crumb rubber (CR) as a substitution for aggregate in concrete is a strategy to mitigate environmental damages caused by this waste. Here, the bond behavior between the steel rebar and high-strength concrete containing CR after exposure heat was studied. Steel fibers (SF) was added in the mix design to evaluate its effect on improving the bond behavior. 108 specimens were fabricated, in which the variables were the volume percentage of CR (0, 5, and 10%), SF volume ratio (0, 0.5, and 1%), applied temperature (200, 400, and 600 °C). Three specimens were fabricated for each composite mixture. Afterward, the pullout test was performed on the hardened specimens to evaluate the bond strength, bond stress-slip behavior, failure mode, and bond strength-compressive strength relationship. The observations showed that incorporating CR lowered the bond strength, and with increasing temperature, this reducing effect increased. In this regard, at the applied temperature of 600 °C, the bond strength of specimens with 5% and 10% CR declined by around 24% and 40%, respectively, compared to that of the reference specimen at the same temperature. Moreover, after testing all the heated specimens, it was found that the reducing impact of temperature rise on the bond strength was negligible up to 200 °C (around 5%), significant up to 400 °C (around 20%), and destructive up to 600 °C (around 65%). Additionally, for the specimens failing in the splitting mode, the effect of incorporating SF was positive, and for the specimens failing in the pullout mode, this effect was negligible and, in some cases, even negative. The empirical results suggest that for the specimen incorporating CR, a greater embedment length must be applied compared to the same specimen without CR. In the end, soft computing methods including gene expression programming (GEP) and artificial neural network (ANN), as two promising techniques, were utilized to predict the bond strength and bond-slip behavior.