The fabrication of a mechanically flexible, piezoelectric nanocomposite material for strain sensing applications is reported. Nanocomposite material consisting of zinc oxide (ZnO) nanostructures embedded in a stable matrix of paper (cellulose fibers) is prepared by a solvothermal method. The applicability of this material as a strain sensor is demonstrated by studying its real-time current response under both static and dynamic mechanical loading. The material presented highlights a novel approach to introduce flexibility into strain sensors by embedding crystalline piezoelectric material in a flexible cellulose-based secondary matrix.