A disposable electrochemical lateral flow paper-based sensing device for heavy metal detection is proposed. The quantification of lead and cadmium in aqueous samples is demonstrated in a range from 10 to 100 ppb with a limit of detection of 7 and 11 ppb respectively. Moreover, the platform itself, which is made of paper, served as a sample pretreatment material due to its filtering properties. Real samples, especially in which the matrix is usually turbid and would in principle need a previous filtration, are successfully analyzed. This lab-on-paper device is simple, low cost, easy to fabricate, and portable, being a promising tool for new point-of-care applications in environmental monitoring, public health, and food safety.