The disposal of potentially toxic element (PTE)-loaded sludge that is produced during industrial or commercial wastewater treatments evoke concerns because of the probability of hazardous environmental consequences. In the current work, we proposed a chelant-assisted decontamination technique of the laboratory-produced PTE-loaded (As, Cd, Pb) polymeric-Fe-coated sludge and subsequent recovery of the chelants and PTEs. The chelant options include both biodegradable (EDDS, GLDA, and HIDS) and non-biodegradable (EDTA) alternatives. The washing performance was compared and discussed in terms of the solution pH and relative stabilities of the complexes of PTEs and chelants in solution. The changes in solution pH or chelants have no significant effect on the chelant-induced removal efficiency of Cd, and the same result was observed for Pb at extreme and moderate acidic pH. The As-extraction rate is also improved with chelant in the solution despite a limited interaction between the chelant and the arsenic species in the solution. The column-packed solid-phase extraction (SPE) system, which was equipped with macrocycle, chelating resin, or ion-exchange resin, was used to explore the corresponding separation performance of the PTEs and chelant. The macrocycle-equipped SPE system shows better selectivity than other SPEs in terms of extraction and recovery performance of the PTEs regardless of the chelants. Some unique points of the proposed process are minimum environmental burden due to the use of biodegradable materials in the washing solution and cost minimization by recycling the ingredients.