This paper describes the fabrication and characterization of a hybrid nanostructure comprised of carbon nanotubes (CNTs) grown on graphene layers for supercapacitor applications. The entire nanostructure (CNTs and graphene) was fabricated via atmospheric pressure chemical vapor deposition (APCVD) and designed to minimize self-aggregation of the graphene and CNTs. Growth parameters of the CNTs were optimized by adjusting the gas flow rates of hydrogen and methane to control the simultaneous, competing reactions of carbon formation toward CNT growth and hydrogenation which suppresses CNT growth via hydrogen etching of carbon. Characterization of the supercapacitor performance of the CNT-graphene hybrid nanostructure indicated that the average measured capacitance of a fabricated graphene-CNT structure was 653.7 μF cm(-2) at 10 mV s(-1) with a standard rectangular cyclic voltammetry curve. Rapid charging-discharging characteristics (mV s(-1)) were exhibited with a capacitance of approximately 75% (490.3 μF cm(-2)). These experimental results indicate that this CNT-graphene structure has the potential towards three-dimensional (3D) graphene-CNT multi-stack structures for high-performance supercapacitors.