<p>Water resources are contaminated by heavy metals and other pollutants from both natural sources and industrial emissions. Therefore, innovative solutions are needed to alleviate the growing pollution and poisoning of water resources, which is a major global issue known as the water crisis. Nanotechnology offers promising opportunities to develop efficient and sustainable water treatment technologies. Magnetic separation has shown exceptional performance in removing contaminants from water. Surface-modified magnetite nanoparticles can be used as adsorbents to treat water. Graphene-based nanocomposites also have shown an effective adsorbing property, but take a long time to process and not cost-effective. However, magnetite–graphene nanocomposites have revealed excellent adsorbing properties and could be used as a good absorbent to remove pollutants from water effectively. These nanocomposites are biodegradable in nature. This review provides an overview of the potential and approaches of magnetite–graphene nanocomposites to treat contaminated water and remove unwanted metal ions, toxic organic impurities, and radioactive ions. </p>