The development of strain sensors featuring both ultra high sensitivity and high stretchability is still a challenge. We demonstrate that strain sensors based on fragmented single-walled carbon nanotube (SWCNT) paper embedded in poly(dimethylsiloxane) (PDMS) can sustain their sensitivity even at very high strain levels (with a gauge factor of over 10(7) at 50% strain). This record sensitivity is ascribed to the low initial electrical resistance (5-28 Omega) of the SWCNT paper and the wide change in resistance (up to 10(6) Omega) governed by the percolated network of SWCNT in the cracked region. The sensor response remains nearly unchanged after 10 000 strain cycles at 20% proving the robustness of this technology. This fragmentation based sensing system brings opportunities to engineer highly sensitive stretchable sensors.