Catalyst degradation is one major challenge preventing the worldwide commercialization of the Proton Exchange Membrane Fuel Cells. In this study, we investigate the development of a novel hierarchical carbonaceous support for the platinum catalysts, called graphene-carbon nanotube hybrids (GCNT), and its degradation behavior during an accelerated degradation test. The carbon support is fabricated by growing graphene directly onto carbon nanotubes to form a unique all-carbon nanostructure possessing both an ultra-high density of exposed graphitic edges of graphene and a porous structure of carbon nanotubes. The GCNT-supported platinum catalyst exhibits a higher intrinsic catalytic activity than a carbon black-supported platinum catalyst, and much higher than a CNT-supported platinum catalyst. The enhanced catalytic activity of the GCNT-supported platinum catalyst is explained by the high graphitic edge density which promotes the catalytic reactions on platinum catalyst. The GCNT-supported platinum catalyst also exhibits a superior electrochemical stability over that of the carbon black-supported platinum catalyst, explained by the high crystallinity of the GCNT support. The superior stability is expressed by a lower loss in polarization performance, a smaller increase in charge transfer resistance, a lower loss in the platinum electrochemical surface area, a lower rate of carbon corrosion, and a more stable catalyst microstructure.