Flexible, sensitive, and low-cost stress sensors are highly desirable in applications such as electronic skin, robot sensor, structural health monitoring, rehabilitation, personal health monitoring, and sport performance monitoring, etc. However, conventional metal-foil and semiconductor slab stress sensors are limited to applications on both relatively stiff substrates and strains under 5% (beyond which the sensor fails mechanically), and therefore are unsuitable for flexible devices. In this work, we demonstrate the fabrication of a simple-structured, low-cost flexible stress sensor based on waste paper. First, low density carbon sponge (CS) with moderate electrical conductive were prepared from waste paper via a simple pyrolysis process. Flexible and electrical conductive CS/polydimethylsiloxane (PDMS) composites were fabricated by vacuum assisted infusion of PDMS resin into CC scaffold. Based on the CS/PDMS composites prepared, a simple yet highly sensitive stress sensor was developed. To demonstrate the feasibility of CS/PDMS sensor as wearable device, a “smart” sport shoe integrated with CS/PDMS sensor was fabricated. The real time sport performance, such as walking, jogging, and running, can be well monitored. In addition, real time breathing detection was carried out by integrating the CS/PDMS sensor with a waist belt. Three breathing patterns, namely, normal breathing, breath holding, and deep breathing, can be easily distinguished from the relative changing of resistance (RCR) response curve. Notably, the device fabrication process is simple, chemical-free, and scalable with low-cost waste paper as raw materials. The CS/PDMS composites are believed to have promising potential applications in wearable electronic devices such as, human-machine interfacing devices, prosthetic skins, sport performance, and health monitoring.