The development of disposable sensors that can be easily adapted to every analytical problem is currently a hot topic that is revolutionizing many areas of science and technology. The need for decentralized analytical measurements at real time is increasing for solving problems in areas such as environment pollution, medical diagnostic, food quality assurance, etc., requiring fast action. Despite some current limitations of these devices, such as insufficient detection capability at (ultra)trace level and risk of interferent effects due to matrix, they allow low-cost analysis, portability, low sample consumption, and fast response. In the last years, development of paper-based analytical devices has undergone a dramatic increase for on-site detection of toxic metal ions and other pollutants. Along with the great availability of cellulose substrates, the immobilization of receptors providing enhanced recognition ability, such as a variety of nanomaterials, has driven the design of novel sensing approaches. This review is aimed at describing and discussing the different possibilities arisen with the use of different nanoreceptors (e.g., plasmonic nanoparticles, quantum dots, carbon-based fluorescent nanoparticles, etc.) immobilized onto cellulose-based substrates for trace element detection, their advantages and shortcomings.