We report the design and fabrication of a highly durable fuel cell electrocatalyst based on double-polymer-coated carbon nanotubes for use in polymer electrolyte membrane fuel cells. The prepared FC catalyst is composed of Pt-deposited polybenzimidazole-coated carbon nanotubes, which are further coated with Nafion. We fabricated MEA using the catalyst and examined the FC performance. By using this electrocatalyst, a high FC performance with a power density of 375 mW/cm² (at 70˚C, 50% relative humidity using air (cathode)/H₂(anode)) was obtained, and a remarkable durability of 500,000 accelerated potential cycles was recorded with only a 5%-loss of the initial FC potential and 20%-loss of the maximum power density, which were far superior properties compared to those of the MEAs prepared using carbon black in place of the carbon nanotubes. The present study indicates that the prepared highly durable fuel cell electrocatalyst is a promising material for the next generation of PEMFCs.