Higher environmental standards have made the removal of arsenic from water an important problem for environmental engineering. Iron oxide is a particularly interesting sorbent to consider for this application. Its magnetic properties allow relatively routine dispersal and recovery of the adsorbent into and from groundwater or industrial processing facilities; in addition, iron oxide has strong and specific interactions with both As(III) and As(V). Finally, this material can be produced with nanoscale dimensions, which enhance both its capacity and removal. The objective of this study is to evaluate the potential arsenic adsorption by nanoscale iron oxides, specifically magnetite (Fe3O4) nanoparticles. We focus on the effect of Fe3O4 particle size on the adsorption and desorption behavior of As(III) and As(V). The results show that the nanoparticle size has a dramatic effect on the adsorption and desorption of arsenic. As particle size is decreased from 300 to 12 nm the adsorption capacities for both As(III) and As(V) increase nearly 200 times. Interestingly, such an increase is more than expected from simple considerations of surface area and suggests that nanoscale iron oxide materials sorb arsenic through different means than bulk systems. The desorption process, however, exhibits some hysteresis with the effect becoming more pronounced with small nanoparticles. This hysteresis most likely results from a higher arsenic affinity for Fe3O4 nanoparticles. This work suggests that Fe3O4 nanocrystals and magnetic separations offer a promising method for arsenic removal.