Biodegradation of carbon-based nanomaterials has been pursued intensively in the last few years, as one of the most crucial issues for the design of safe, clinically relevant conjugates for biomedical applications. In this paper it is demonstrated that specific functional molecules can enhance the catalytic activity of horseradish peroxidase (HRP) and xanthine oxidase (XO) for the degradation of carbon nanotubes. Two different azido coumarins and one cathecol derivative are linked to multi-walled carbon nanotubes (MWCNTs). These molecules are good reducing substrates and strong redox mediators to enhance the catalytic activity of HRP. XO, known to metabolize various molecules mainly in the mammalian liver, including human, was instead used to test the biodegradability of MWCNTs modified with an azido purine. The products of the biodegradation process are characterized by transmission electron microscopy and Raman spectroscopy. The results indicate that coumarin and catechol moieties have enhanced the biodegradation of MWCNTs compared to oxidized nanotubes, likely due to the capacity of these substrates to better interact with and activate HRP. Although azido purine-MWCNTs are degraded less effectively by XO than oxidized nanotubes, the data uncover the importance of XO in the biodegradation of carbon-nanomaterials leading to their better surface engineering for biomedical applications.