We employed an electroless deposition technique to prepare Ni seeds uniformly on a carbon cloth, followed by carbon nanotube (CNT) formation at an elevated temperature. Subsequently, a pulse electrodeposition was used to impregnate PtRu nanoparticles on the CNT structure. Similar procedures were performed on carbon supports including Vulcan XC72R, BP2000, and carbon nanocapsules (CNCs) for comparison purposes. Diffraction patterns from an X-ray confirmed a PtRu alloyed phase. An analysis from inductively coupled plasma-mass spectrometry indicated that the PtRu composition was relatively unchanged. Images from scanning and transmission electron microscopes revealed dense CNTs throughout the carbon cloth with nanoparticulate PtRu evenly impregnated. Considerable PtRu aggregations were found on the CNCs and BP2000. We observed a significantly improved coulomb efficiency and an electrochemically active surface area for the CNT-grown carbon cloth. In both apparent current density and mass activity for methanol electro-oxidation, the CNT-grown carbon cloth revealed the largest values. We attribute the performance enhancement to the large-area CNT structure that allowed facile access of electrolytes.