Highly stretchable electrically conductive hydrogels have been extensively researched in recent years, especially for applications in strain and pressure sensing, electronic skin, and implantable bioelectronic devices. Herein, we present a new cross-linked complex coacervate approach to prepare conductive hydrogels that are both highly stretchable and compressive. The gels involve a complex coacervate between carboxylated nanogels and branched poly(ethylene imine), whereby the latter is covalently cross-linked by poly(ethylene glycol) diglycidyl ether (PEGDGE). Inclusion of graphene nanoplatelets (Gnp) provides electrical conductivity as well as tensile and compressive strain-sensing capability to the hydrogels. We demonstrate that judicious selection of the molecular weight of the PEGDGE cross-linker enables the mechanical properties of these hydrogels to be tuned. Indeed, the gels prepared with a PEGDGE molecular weight of 6000 g/mol defy the general rule that toughness decreases as strength increases. The conductive hydrogels achieve a compressive strength of 25 MPa and a stretchability of up to 1500%. These new gels are both adhesive and conformal. They provide a self-healable electronic circuit, respond rapidly to human motion, and can act as strain-dependent sensors while exhibiting low cytotoxicity. Our new approach to conductive gel preparation is efficient, involves only preformed components, and is scalable.