Carbon nanotubes (CNTs) and graphene are potential candidates for future interconnect materials. CNTs are promising on-chip via interconnect materials due to their readily formed vertical structures, their current-carrying capacity, which is much larger than existing on-chip interconnect materials such as copper and tungsten, and their demonstrated ability to grow in patterned vias with sub-50 nm widths; meanwhile, graphene is suitable for horizontal interconnects. However, they both present the challenge of having high-resistance contacts with other conductors. An all-carbon structure is proposed in this paper, which can be formed using the same chemical vapor deposition method for both CNTs and graphene. Vertically aligned CNTs are grown directly on graphene with an Fe or Ni catalyst. The structural characteristics of the graphene and the grown CNTs are analyzed using Raman spectroscopy and electron microscopy techniques. The CNT-graphene interface is studied in detail using transmission electron microscopic analysis of the CNT-graphene heterostructure, which suggests C−C bonding between the two materials. Electrical measurement results confirm the existence of both a lateral conduction path within graphene and a vertical conduction path in the CNT-graphene heterostructure, giving further support to the C−C bonding at the CNT-graphene interface and resulting in potential applications for all-carbon interconnects.