Carbon nanostructures were grown on the surface of cordierite monoliths using Fe or Co nanoparticles by catalytic chemical vapor deposition (CCVD) with ethanol in order to intensify the interaction of this support with organic contaminants. The materials produced were extensively characterized by X-ray diffraction, thermal analysis, elemental analysis, atomic absorption spectrometry, Raman spectroscopy and scanning and transmission electron microscopies. The materials were tested in the removal of quinoline and methylene blue from liquid solutions. Promising results were attributed to the combined effect of the hydrophobic carbon nanostructures in adsorbing the organic contaminants with cobalt metal cores that are able to promote the oxidation of the adsorbed molecules via a heterogeneous Fenton process.