We report on 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 with specific surface areas of the order of 93 and 66 m2 g−1, compared to approx. 4 m2 g−1 for graphite, decorated with ferromagnetic iron nanoparticles giving coercivity fields postulated to be 216 and 98 Oe, values typical for ferrite magnets, for 3.2 and 13.5 wt% Fe respectively. The strongly magnetic iron nanoparticles are robustly anchored to the GO sheets by a layer of residual graphite, on the order of 5 nm, formed during the pyrolysis of the precursor material. The applicability of the carbon sponges is demonstrated in their ability to absorb, store and subsequently elute an organic dye, Rhodamine B, from water as required. It is possible to regenerate the carbon-iron hybrid material after adsorption by eluting the dye with a solvent to which it has a high affinity, such as ethanol. The use of a carbon framework opens the hybrid materials to further chemical functionalization, for enhanced chemical uptake of contaminants, or co-decoration with, for example, silver nanoparticles for bactericidal properties. Such analytical properties, combined with the material's magnetic character, offer solutions for environmental decontamination at land and sea, wastewater purification, solvent extraction, and for the concentration of dilute species.