Paper has been utilized for centuries by humans for writing, printing, and packaging. It has properties of being flexible, biocompatible, and biodegradable which make it a valuable low cost and environmentally friendly alternative to petrochemical-based materials for applications in robotics, electronics, and microfluidics. In particular, electrically conductive materials, which possess the merits of minimal weight and good processing ability, can be integrated into the manufacturing process of structural parts, allowing the implementation of a sensor function. By mixing multi-walled carbon nanotubes (MWCNTs), sheets of hexagonally packed carbon atoms rolled into concentric seamless cylinders, with insulating cellulose fibers, we were able to produce a conductive paper that retains its strength and exhibits sensitive resistive changes when exposed to water and humidity. The fabrication process was based on traditional papermaking methods and included the refining of unbleached softwood Kraft fibers, the suspension of cellulosic fibers in MWCNT–cationic polymer mixtures, and the filtration, pressing, and drying of the resulting pulp to prepare handsheets with grammage of 60 g/m2. The as-prepared MWCNT–cellulose composite papers were analyzed by electron microscopy and their water sensing abilities were examined. Results showed that, unlike most common petrochemical-based materials that are not sensitive to polar water molecules, the relative electrical resistance of the paper composites significantly increased under water and returned almost to their initial level of resistance after drying, with very fast and reproducible signals over multiple immersion/drying cycles. Future large-scale production of the paper is planned to explore industry-feasible methods.