In this study, the removal mechanisms of sulfidated nanoscale zero-valent iron (S-nZVI) toward EDTA-chelated CdII (CdII-EDTA) and the detailed effects of some critical factors on CdII-EDTA removal by S-nZVI were systematically investigated. The results showed that the removal capacity of S-nZVI toward CdII-EDTA within 90 min of reaction was 746.6 mg/g (when the initial concentration of CdII-EDTA, the dosage of S-nZVI, and the initial solution pH were 300.0 mg CdII/L, 0.3 g/L, and 2.6, respectively), which was 6.2 and 2.5 times higher than that of nZVI and Na2S, respectively, indicating that Fe and S had coupled effect on CdII-EDTA removal. The removal mechanisms of CdII-EDTA by S-nZVI consisted of two-step replacement reactions. In brief, FeIII generated from the corrosion of S-nZVI firstly replaced the CdII in CdII-EDTA, and then the decomplexed CdII ions were immobilized by occurring the second-step replacement reaction with FeS in S-nZVI and forming CdS phase. Batch experiment results indicated that the removal of CdII-EDTA by S-nZVI decreased as the initial CdII-EDTA concentration increased and S-nZVI dosage decreased. Under the same S-nZVI dosage (0.3 g/L) and initial CdII-EDTA concentration (300.0 mg CdII/L), the acidic initial pH (pH0 = 2.6) was favorable for the removal of CdII-EDTA. This study demonstrated that S-nZVI could be a viable choice for the CdII-EDTA-contaminated wastewater treatment.