Intrinsic self-healing and highly stretchable electro-conductive hydrogels demonstrate wide-ranging utilization in intelligent electronic skin. Herein, we propose a new class of strain sensors prepared by cellulose nanofibers (CNFs) and graphene (GN) co-incorporated poly (vinyl alcohol)-borax (GN-CNF@PVA) hydrogel. The borax can reversibly and dynamically associate with poly (vinyl alcohol) (PVA) and GN-CNF nanocomplexes as a cross-linking agent, providing a tough and flexible network with the hydrogels. CNFs act as a bio-template and dispersant to support GN to create homogeneous GN-CNF aqueous dispersion, endowing the GN-CNF@PVA gels with promoted mechanical flexibility, strength and good conductivity. The resulting composite gels have high stretchability (break-up elongation up to 1000%), excellent viscoelasticity (storage modulus up to 3.7 kPa), rapid self-healing ability (20 s) and high healing efficiency (97.7 ± 1.2%). Due to effective electric pathways provided by GN-CNF nanocomplexes, the strain sensors integrated by GN-CNF@PVA hydrogel with good responsiveness, stability and repeatability can efficiently identify and monitor the various human motions with the gauge factor (GF) of about 3.8, showing promising applications in the field of wearable sensing devices.