Adopting robust, stretchable, recyclable and self-healable elastomers composed of renewable resources is of great importance, but is rarely reported due to the irreversible cross-linked network. Here, we propose a simple and efficient method to prepare a robust and stretchable rubber network with recyclable and self-healable capabilities. TEMPO oxidized cellulose nanocrystals (TOCNs) with a large number of carboxyl groups were used as both the reinforcement phase and covalent cross-linkers for epoxidized natural rubber (ENR). FTIR results indicate that interfacial ester bonds were formed between carboxyl groups and epoxy groups. The covalent rubber network exhibited high tensile stress (>5 MPa) and fracture strain (>600%). Additionally, the network with exchangeable β-hydroxyl ester bonds at the rubber–TOCN interface can alter the network topology via transesterification reactions at evaluated temperatures. Therefore, the samples can achieve up to ∼85% recovery efficiency and ∼80% self-healing efficiency, exhibiting excellent reprocessing and self-healing behaviors. In addition, the samples can also be used as substrates for preparing flexible electronic devices, which exhibited excellent self-healing of electrical conductivity after damage.