We describe the fabrication of a well-defined carbon nanotube (CNT)-based composite, in which the CNTs are individually wrapped by a polymer in a homogeneous fashion and platinum nanoparticles (Pt) are immobilized on the polymer-wrapped CNTs. Polybenzimidazoles (PBIs) are used as the wrapping polymer since a strong adsorption of PBIs onto the CNT surfaces enables the exfoliation of CNT bundles and nanometre-thick PBI wrapping layer serves as a glue for the efficient immobilization of Pt. We demonstrate the use of the composite for the polymer electrolyte fuel cell (PEFC) electrocatalyst. The well-defined interfacial nanostructure of the composite enables efficient reactant diffusion, resulting in good oxygen reduction reaction activity. Single cell tests reveal that the ultra-thin PBI-wrapping layer around the CNTs serves as a proton conducting layer to deliver protons in the catalyst membrane. PEFCs using the composite show an excellent fuel cell performance at 120 °C under non-humid atmosphere, whereas the conventional Nafion-based PEFCs are not workable in such condition. Unique combination of the CNTs and PBIs provides a promising route for the next-generation high temperature PEFC.