Worldwide, industrialization led to the severe pollution causing long-term damage to the natural resources. Recent focus of water remediation technology is to develop materials which have high capacity to remove contaminants, low cost, easy retrieval and environmental compatibility. In this regard, this study aimed to prepare a nanocomposite of non-toxic and biodegradable polymer such as carboxymethyl cellulose (CMC) and magnetic Fe3O4 nanoparticles. The study also investigates the efficiency CMC-Fe3O4 synergies for the removal of toxic heavy metal like arsenic in water. CMC-Fe3O4 nanocomposite was prepared by dispersing as-prepared Fe3O4 nanoparticles in the polymer matrix in 2:1 ratio via ultrasonication. As prepared material was characterized by using X-ray diffractometer, field emission-scanning electron microscopy, energy dispersive spectroscopy, high-resolution transmission electron microscopy and Fourier transform infrared spectroscopy that confirms the formation of nanocomposite. The nanocomposite demonstrated high adsorption capacity of 287.19 mg.g−1 towards 300 mg L−1 As (III) at optimum experimental conditions such as 30 min of equilibration using 0.025 g of nanoadsorbent at neutral pH. The adsorption process was well described by Langmuir isotherm model, best fitted with pseudo-second-order kinetics. Biocompatibility and easy magnetic separation of nanoadsorbent ensures the environmental safety.