Among the various carbon-based nanomaterials, carbon nanotubes and graphene have in the last few years emerged as two materials with the potential to move forward the field of nanomedicine. Indeed, modifying and engineering their basic graphitic structures in order to improve their biocompatibility have led to the demonstration of their possible use as delivery systems, biosensors or composites for tissue engineering. But while functionalised carbon nanomaterials present reduced toxicity and great biomedical promise, they are still viewed with scepticism owing to the paradigm that their physico-chemical characteristics make them non-biodegradable. Recently, different studies have however uncovered that peroxidase enzyme-based processes could lead to their oxidation and biodegradation. This chapter provides the current knowledge on this topic including the proposed mechanism for enzymatic-catalysed biodegradation. In the context of biomedical use, these new findings offer novel perspectives for carbon nanomaterials and also stress the need for future investigations that could reveal how to promote or inhibit their biodegradation – depending on the biomedical application desired. Directions for prospective researches that aim to make carbon nanomaterials more degradable and allow their translation into the clinic are proposed.