A novel voltammetric method for the sensitive and selective determination of cadmium and lead ions using screen-printed carbon electrodes (SPCEs) modified with carbon-deposited natural halloysite (C_Hal) and multi-walled carbon nanotubes (MWCNTs) was developed. The electrochemical properties of the proposed sensor were investigated by electrochemical impedance spectroscopy (EIS) and cyclic voltammetry (CV), while the morphology and structure were established by scanning electron microscopy (SEM) and X-ray powder diffraction (XRD). A two-factorial central composite design (CCD) was employed to select the composition of the nanocomposite modifying the electrode surface. The optimal measuring parameters of differential pulse anodic stripping voltammetry (DPASV) used for quantitative analysis were established with the Nelder–Mead simplex method. In the analytical investigation of Cd(II) and Pb(II) ions by DPASV, the MWCNTs/C_Hal/Nafion/SPCE exhibited a linear response in the concentration range of 0.1–10.0 µmol L⁻¹ (for both ions) with a detection limit of 0.0051 and 0.0106 µmol L⁻¹ for Pb(II) and Cd(II), respectively. The proposed sensor was successfully applied for the determination of metal ions in different natural water and honey samples with recovery values of 96.4–101.6%.