Carbon nanostructures (e.g., fullerenes, CNTs, graphene, nanohorns, nanodiamonds) play a key role in the development of nanomedicines. Here we analyze opportunities and barriers for their application in clinical settings. In particular, we discuss the unique properties of certain carbon nanostructures that allow for innovative solutions in theranostics, as well as current pitfalls around clinical applications of the EPR effect, the formation of the protein corona, and how functionalization of CNTs is a key tool to modulate their biodistribution and toxicity.