Extracellular polysaccharide (EPS) from Klebsiella oxytoca was chemically modified to increase net negative charge in order to expand the efficiency of metal binding. Chlorosulfonic acid (CSA) or a complex of dimethylformamide and sulfur trioxide (DMF–SO3) was used to introduce sulfate substituents onto the native polymer. Additionally, sequential treatment with divinylsulfone (DVS) and glycine or DVS and iminodiacetic acid (IDA) was used to introduce carboxyl residues. Native EPS exhibited a molecular mass distribution of 1500–1700 kDa and removed 38% and 19%, respectively, of lead and cadmium ions. Modification with CSA resulted in a reduction of molecular mass to 450–600 kDa and a removal from solution of lead and cadmium of 75% and 66%, respectively. Modification of EPS with the DMF–SO3 complex, while it did not affect the molecular mass of the polymer, resulted in decreased levels of lead and cadmium removal. Covalent substitution of EPS with DVS–glycine resulted in an increase of molecular mass to 3000 kDa and lead and cadmium removals of 46% and 47%, respectively. Modification of EPS with DVS–IDA increased molecular mass to 2200 kDa and demonstrated lead and cadmium removals of 57% each. Immobilization of native EPS and of the CSA and DVS–IDA modifications to oxirane–acrylic beads resulted in significant increases in metal binding per gram of bound polymer. This suggests a method for metal ion recovery using chelate desorption.