Although carbon nanotubes (CNTs) are well known to have a strong affinity to various heavy metals in aqueous solution, little research has been dedicated to exploit their use in fixed-bed water treatment systems (e.g., trickling filters). In this work, batch sorption and fixed-bed experiments were conducted to examine the ability of functionalized multi-walled CNTs as filter media to remove two heavy metal ions (Pb2+ and Cu2+) from infiltrating water. Batch sorption experiments confirmed the strong sorption affinity of the CNTs for Pb2+ and Cu2+ in both single and dual metal solution systems. In addition, sonication-promoted dispersion of the CNT particles enhanced their heavy metal sorption capacity by 23.9–32.2%. For column experiments, laboratory-scale fixed-bed columns were packed with CNTs and natural quartz sand by three different packing: layered, mixed, and deposited. While all the three packing methods enhanced the fixed-bed filtering efficiency of Pb2+ and Cu2+ from single and dual metal systems, the CNT-deposited packing method was superior. Although the amount of the CNTs added into the fixed-bed columns was only 0.006% (w/w) of the sand, they significantly improved the fixed-bed’s filtering efficiency of Pb2+ and Cu2+ by 55–75% and 31–57%, respectively. Findings from this study demonstrate that functionalized multi-walled CNTs, together with natural sand, can be used to effectively and safely remove heavy metals from water.