In present paper, the influence of the initial pH and concentration of Pb2+ on its adsorption by the natural (NZA) and Fe(III)-modified zeolite-alginate beads (FeA) was studied. Results showed that modification of the starting materials have a positive effect on their adsorption capacities (102 and 136 mg/g for the NZA and FeA, respectively). After encapsulation, the mechanism of lead adsorption by both adsorbents was changed and ion exchange dominates. The best adsorption was achieved for initial pH > 3.8. Cation exchange capacity, structural properties, and hydrophobicity of samples were also determined, and the presence of the alginate has no significant influence on investigated properties of samples. Experiments on wastewater from tailings of lead and zinc mine Grot, Serbia, showed that after treatment with both adsorbents, the content of the most abundant heavy metals (Pb, Zn, Hg, and Mn) significantly decreased.