Combining the advantages of high thermal conductivities and low graphene contents to fabricate polymer composites for applications in thermal management is still a great challenge due to the high defect degree of exfoliated graphene, the poor orientation of graphene in polymer matrices, and the horrible phonon scattering between graphene/graphene and graphene/polymer interfaces. Herein, mesoplasma chemical vapor deposition (CVD) technology was successfully employed to synthesize vertically aligned graphene nanowalls (GNWs), which are covalently bonded by high-quality CVD graphene nanosheets. The unique architecture leads to an excellent thermal enhancement capacity of the GNWs, and a corresponding composite film with a matrix of polyvinylidene fluoride (PVDF) presented a high through-plane thermal conductivity of 12.8 ± 0.77 W m-1 K-1 at a low filler content of 4.0 wt%, resulting in a thermal conductivity enhancement per 1 wt% graphene loading of 1659, which is far superior to that using conventional graphene structures as thermally conductive pathways. In addition, this composite exhibited an excellent capability in cooling a high-power light-emitting diode (LED) device under real application conditions. Our finding provides a new route to prepare high-performance thermal management materials with low filler loadings via the rational design of the microstructures/interfaces of graphene skeletons.