Arsenic contamination of drinking water is a major public health concern affecting more than 200 million people globally. Iron(Fe)-based adsorbents though promoted for aqueous arsenic removal because of their low cost and easy availability, their field application is limited due to their low efficiency and slow adsorption kinetics. In this work, two graphene oxide (GO)-Fe nanohybrids, namely GO-supported nano magnetite (GM) and GO-supported nanoscale zero-valent iron (GFeN), were compared for arsenic removal. Controls were run with bare (i.e., no GO) nanoscale zero-valent iron (FeNP) and nano magnetite (M). GFeN worked more efficiently (>90%) over a wide pH range (3-9) for both the inorganic arsenic species, As(III) and As(V). GM worked well at pH 3 (>90% efficient) for As(V), and pH 9 (80%) for As(III). GFeN exhibited better aqueous dispersibility with a zeta potential of -21.02 mV. In GFeN and FeNP, surface complexation was dominant in the adsorption of both As(III) and As(V), and electrostatic attraction played a limited role. In GM and M, As(V) removal was controlled by electrostatic attraction while As(III) adsorption was ligand exchange and surface complexation. The arsenic removal data based on normalized iron content in the adsorbents indicated that the nanohybrids (GFeN and GM) removed arsenic more efficiently compared to the bare nanoparticles (FeNP and M) with GFeN performing the best. Arsenic adsorption capacities of GFeN were found to be 306 mg/g for As(III) and 431 mg/g for As(V). The GO-sheets in GFeN acted as reservoirs for the electrons released during surface corrosion of the FeNPs. The stored electrons were transferred back to the FeNPs to reduce the oxidized iron surface, and the rejuvenated surface helped in additional arsenic removal. The arsenic desorption pattern from two As(V)-sorbed nanohybrids (GFeN and graphene oxide-supported ceria (GO-CeO2)) was studied. GFeN released ~5.73% and GO-CeO2 released ~0.94% of sorbed arsenic over a period of two years. While sorbed arsenic remained as As(V) on the GFeN surface, some As(V) in GO-CeO2 got reduced to As(III). The surface oxide composition in GFeN (FeOOH and Fe2O3) and GO-CeO2 (Ce3+/Ce4+ ratio) underwent changes over time and that played a role in arsenic desorption.