In this study, starch-stabilized nanoscale zero-valent iron (S-nZVI) was produced using the liquid-phase reduction method. It was used to remove chromium from wastewater, and compared to a commercial nanoscale zero-valent iron (C-nZVI). Both nZVIs were characterized by scanning electron microscopy (SEM), X-ray diffraction (XRD) and X-ray photoelectron spectroscopy (XPS). The characterization results showed that S-nZVI had smaller particles and a more uniform particle size distribution than C-nZVI. Both nZVIs showed a core-shell structure with the Fe0 core prominently surrounded by less iron oxides of Fe2+ and Fe3+. The optimal application methods to remove Cr(VI) from wastewater were also explored. The results showed that both the removal efficiencies of total Cr and Cr(VI) increased with increases in the addition of nZVIs, while the removal efficiencies of total Cr and Cr(VI) by S-nZVI were clearly higher than that of C-nZVI, especially in a low pH range (pH = 1.0-6.0). This research indicated that starch-stabilized nanoscale zero-valent iron is a valuable material to remove heavy metals from wastewater due to its stability and high reactivity.