Mechanically robust and self-healing rubbers are highly desired to satisfy the increasing demand of high-performance smart tires and related materials. Herein, a self-healing rubber nanocomposite with enhanced mechanical and self-healing performance based on Diels-Alder chemistry has been investigated. The furfuryl grafted styrene-butadiene rubber and furfuryl terminated MWCNT (MWCNT-FA) are reacted with bifunctional maleimide to form a covalently bonded and reversibly cross-linked rubber composite. Obvious reinforcing effect is obtained at high cross-linking density. Over 200-300% increase in the Young's modulus and toughness can be achieved in the rubber nanocomposites with 5 wt% MWCNT-FA. Meanwhile, the healing efficiency increased with MWCNT-FA content. MWCNT-FA plays dual roles of effective reinforcer and a kind of healant.