A novel type of carbon paste electrode modified by multi-walled carbon nanotubes and antimony trioxide (Sb2O3/CNTCPE) was applied for square wave anodic stripping voltammetry (SWASV) of Cd2+ and Pb2+. Important parameters (deposition potential, deposition time, HCl concentration) were optimized and linear concentration dependence was obtained in the range of 10–100 ppb with LOD 1.7 ppb for Cd2+ and 1.2 ppb for Pb2+. The practical applicability was tested on the determination of Cd2+ and Pb2+ in tap water. The potentiometric stripping analysis at Sb2O3/CNTCPE was tested for the determination of Cd2+ and Pb2+ to compare this method with SWASV.