In this work, nanofibrillated cellulose (NFC) has been used as a sensitive matrix to develop electrochemical sensor trace heavy metal ions quantification via differential pulse anodic stripping voltammetry (DPASV). Cellulose fibers from Eucalyptus were fibrillated into nano-sized fibrils throughout the homogenization process. To facilitate the fibrillation process, fibers were previously oxidized under neutral conditions to bring the carboxyl content up to 500 NFC layer was deposited on a carbon glassy electrode (CGE) by simple adsorption. The adopted DPASV method was achieved by optimizing some parameters such as the accumulation time, the deposition time and the deposition potential. As a result, the modified electrode with nanofibrillated cellulose exhibited reproducible response, high sensitivity and good stability for Cd(II), Pb(II) and Hg(II) ions. The developed ion sensor was used for heavy metal determination in seawater.