We report a method for the synthesis of two and three dimensional carbonaceous sponges produced directly from graphene oxide (GO) into which functionalized iron nanoparticles can be introduced to render it magnetic. This simple, low cost procedure wherein an iron polymeric resin precursor is introduced into the carbon framework results in carbon-based materials, decorated with ferromagnetic iron nanoparticles, with specific surface areas of the order of 93 and 66 m2/g for 3.2 and 13.5 wt. % Fe, compared to approx. 4 m2/g for graphite. The iron nanoparticles with strong magnetic properties are robustly anchored to the GO sheets by a layer of residual graphite, formed during the pyrolysis of the precursor material. This graphite coating, on the order of 5 nm, provides the hard protective layer, which is resistant to chemical attack. The coercivity field of these magnetic carbon sponges is postulated to be 216 and 98 kG respectively for 3.2 and 13.5 wt. % Fe. The applicability of these carbon sponges is demonstrated in their ability to absorb, store and subsequently elute organic dyes from water as required. Such analytical properties, combined with the material’s magnetic character, offer solutions for wastewater purification, solvent extraction, mop-up of environmentally damaging compounds at land and sea, biomolecular sample concentration, and for the concentration of dilute species.