Nanomaterials possess unique features which make them particularly attractive for biosensing applications. In particular, carbon nanotubes (CNTs) can serve as scaffolds for immobilization of biomolecules at their surface, and combine several exceptional physical, chemical, electrical, and optical characteristics properties which make them one of the best suited materials for the transduction of signals associated with the recognition of analytes, metabolites, or disease biomarkers. Here we provide a comprehensive review on these carbon nanostructures, in which we describe their structural and physical properties, functionalization and cellular uptake, biocompatibility, and toxicity issues. We further review historical developments in the field of biosensors, and describe the different types of biosensors which have been developed over time, with specific focus on CNT-conjugates engineered for biosensing applications, and in particular detection of cancer biomarkers.