Stretchable strain sensors, as crucial components in wearable intelligent devices, have become one of the recent research hotspots with promising potential in human-interactive, personal health monitoring, and flexible smartphones. Graphene-based materials have been reported for high-performance strain sensors. However, there still remain some limitations such as their high production cost and low sensitivity and stretchability. Herein, a highly stretchable and ultra-sensitive strain sensor based on nickel nanoparticles and a graphene-coated polyurethane sponge (Ni@GPUS) ternary hybrid material has been reported. Herein, Ni@GPUS was fabricated via a series of techniques including preparation of a graphene-coated polyurethane sponge, electrodeposition of nickel nanoparticles, and encapsulation by polydimethylsiloxane. The obtained sensors can be stretched up to 65% and exhibit a remarkable gauge factor of up to 3360.09. Furthermore, a fast signal response (<100 ms) and 1000 cycles of stretching and bending prove the rapid steady state response and long-term durability of the sensor, respectively. In addition, the working mechanisms of the sensor have been proposed. Moreover, the strain sensor was used as a bodily motion sensor to monitor finger bending and facial muscle tension, showing great potential in the fields of flexible, stretchable, and wearable electronics.