In this study, halloysite-Fe3O4 composites were synthesized by a chemical-precipitation method to facilitate magnetic separation of the sorbents from aqueous solution. The research focused on the effect of Fe3O4 phase on the halloysite sorption properties. The X-ray diffraction (XRD) results confirmed successful deposition of Fe3O4 particles on a halloysite surface. They showed that the coating with Fe3O4 particles enhanced the halloysite adsorption affinity toward Cd(II) and Pb(II). The highest adsorption capacity was determined for the composites having 10% of the surface deposited with Fe3O4. In this case, the adsorption capacity for Cd(II) and Pb(II) was 33 and 112 mmol·kg−1, respectively. The point of zero charge (pHPZC) and desorption results indicated that the removal mechanism of metals is mainly related to chemisorption involving reaction with hydroxyls of either halloysite or Fe3O4 phase. The ion exchange is of limited importance due to the low cation exchange capacity (CEC) of halloysite - Fe3O4 composites.