The combination of different nanobuilding blocks in a single heterostructure can lead to materials with improved properties by selecting components with the desired characteristics for a specific application. Carbon-based nanomaterials demonstrated to be highly suitable as support for the elaboration of heterostructures. Atomic layer deposition proved to be a technique of choice for the coating of nanostructured carbon materials. These heterostructures find applications in various areas such as electronics, sensors and energy storage and conversion. Because the chemical inertness of the graphitic carbon inhibits the initiation of ALD film growth, numerous surface functionalization approaches have been investigated in order to provide the required nucleation sites. The different strategies employed for the ALD onto carbon nanotubes, graphene, graphite and other nanostructured carbon materials (e.g. carbon black, fibers) will be described. The peculiarity of ALD for tailoring the chemical, structural and morphological properties of the deposited material will be discussed. Finally, in order to highlight the importance of this class of materials, possible applications in energy storage and conversion, catalysis and gas sensing devices are also reviewed.