Nanoscale-zero valent iron (NZVI) is an effective groundwater remediation media because it can quickly reduce and absorb contaminants. However, NZVI quickly agglomerates in aqueous systems, reducing its remediation capacity. This work investigated coating NZVI with native and modified rice, wheat, maize, and tapioca starches to improve colloidal stability. Colloidal stability studies were conducted with native and commercially available starches; tapioca starch modified with 2-Octen-l-ylsuccinic anhydride (OSA) was the best. Four concentrations of OSA-tapioca starch were prepared (3, 15, 35, and 50% w/w). NZVI coated with 35% OSA-modified tapioca starch (concentration = 10 g L-1) kept 66% of the coated particles suspended after 2 hours (compared to 4% of bare particles, p = 0.000). Bare NZVI reduced significantly more nitrate (20 mg L-1) than coated NZVI (p =0.000). Bare and coated NZVI provided the same nitrate reduction at 40 and 60 mg L-1 (p = 0.939 and p = 0.815, respectively).