Magnetic separations at very low magnetic field gradients (<100 tesla per meter) can now be applied to diverse problems, such as point-of-use water purification and the simultaneous separation of complex mixtures. High–surface area and monodisperse magnetite (Fe3O4) nanocrystals (NCs) were shown to respond to low fields in a size-dependent fashion. The particles apparently do not act independently in the separation but rather reversibly aggregate through the resulting high-field gradients present at their surfaces. Using the high specific surface area of Fe3O4 NCs that were 12 nanometers in diameter, we reduced the mass of waste associated with arsenic removal from water by orders of magnitude. Additionally, the size dependence of magnetic separation permitted mixtures of 4- and 12-nanometer–sized Fe3O4 NCs to be separated by the application of different magnetic fields.