In this study, the in situ synthesis of Fe3O4 nanoparticles on the surface of two-dimensional rGO nanosheets was performed. Fe3O4/rGO nanocomposites with a different degree of rGO reduction were obtained using various mass ratios between Fe3O4 and rGO, and different synthesis times. A comprehensive analysis of the morphology, microstructure, magnetic properties and the reduction degree of the synthesized rGO and Fe3O4/rGO nanocomposites was performed. The synthesis conditions were established for the preparation of a Fe3O4/rGO nanocomposite with the highest degree of rGO reduction and Fe3O4 phase purity. An increase in crystallite size and average particle size with the increase in the Fe3O4:rGO mass ratio (from 1:1 to 6:1) was revealed. For the first time, a saturation point for the amount of phase-pure Fe3O4 nanoparticles on the rGO surface was determined, as was a specific ratio of magnetite to rGO at which saturation occurred. Examination of the adsorption isotherms and kinetics indicated that the magnetic Fe3O4/rGO nanocomposite can serve as an effective adsorbent for arsenic ion (As3+) removal from water, with an excellent removal capacity of 14 mg g−1. In addition, the adsorption rate of the Fe3O4/rGO nanocomposite enabled 81% As3+ uptake within 1 min, which is superior to the literature data.