The catalytic reactivity of synthetic bare magnetite nanoparticles, activated carbon supported magnetite (AC-Mt), and graphene oxide supported magnetite (GO-Mt) for heterogeneous Fenton-like oxidation of methylene blue (MB) were compared, in order to investigate how the structural features of the support impact catalytic activity of the nanocomposites. The different effects of AC and GO on MB removal rate, hydroxyl radical ([radical dot]OH) production, iron leaching, and surface deactivation have been systematically studied. The rate constant of MB removal by AC-Mt was 0.1161 min-1, one order of magnitude larger than the value of bare magnetite nanoparticles (0.0566 min-1). The higher catalytic activity of AC-Mt might be attributed to the larger reactive surface area of well-dispersed magnetite for [radical dot]OH production and the recharge of the magnetite surface by the AC support via Fe-O-C bonds. However, the removal rate of MB by GO-Mt was one order of magnitude slower than that of bare magnetite nanoparticles under the same experimental conditions, presumably due to the wrapping of GO around magnetite nanoparticles or extensive aggregation of GO-Mt composites. These findings revealed the significant influence of support structure on the catalytic activity of carbon-supported magnetite nanocomposites, which is important for the development of efficient magnetite-based catalysts for wastewater treatments.