This study demonstrates the potential of using multi-scale hierarchical carbon structures as robust, reusable solids suitable for removal of aqueous pollutants such as dye molecules from wastewater. Carpet-like vertical arrays of carbon nanotubes (CNT) were attached on surfaces of porous carbon foams by pre-coating with silica buffer layer followed by chemical vapor deposition (CVD). The surface morphology and specific surface areas were varied by controlling the buffer layer thickness and CVD deposition times. Surface characteristics have been correlated with adsorption thermodynamics and kinetics by investigating the removal rates of methylene blue (MB) dye in simulated water. The results show that MB adsorption capacity correlates well with total CNT surface area in the carpet, indicating full utilization of the nanotube surfaces. Adsorption rates fit well with pseudo second order kinetics model. Maximum MB adsorption capacity of the CNT surfaces in this structure was estimated by extrapolating equilibrium adsorption amounts at different dye concentrations using the Langmuir isotherm. This was found to be about 43.5 mg/g, which compares favorably with adsorption capacity of isolated nanotubes. It must be noted that whereas isolated nanotubes can disperse in the liquid and pose environmental threats, the hierarchical solids as demonstrated in this study can be repeatedly agitated in water without the loss of CNT or performance deterioration. These results indicate promising application potential for these types of hybrid materials in environmental purification applications