Both carbon nanotube (CNT) and graphene exhibit excellent properties and have many potential applications in integrated circuits, composite materials, thermal management, sensors, energy storage, and flexible electronics. However, their superior properties are confined to one or two dimensions, thus limiting their utility in interconnects or thermal interface materials that require a 3D structure for efficient electron and/or phonon transport. It is conceivable that a combined CNT-graphene structure would provide new opportunities for realizable applications in these and other fields. In recent years, numerous results on synthesis, structural analyses, theoretical modeling, and potential applications of various CNT-graphene heterostructures have been reported. In this review, we summarize the possible structures that can be formed by connecting CNT and graphene. We then report existing experimental efforts to synthesize the heterostructures based on growth method, catalyst design, and the resulting properties. Also, theoretical studies on various heterostructures are reviewed, with the focus on electron and thermal transport within the heterostructure and across the CNT-graphene interface. Several potential applications are briefly discussed, and a combined theoretical and experimental approach is proposed with the objective of enhancing the understanding of the CNT-graphene heterostructure and attaining a realistic assessment of its feasibility in practical applications.