In polymer electrolyte membrane fuel cells (PEMFC) a fuel—usually hydrogen—and oxygen are combined to produce electricity and water in an electrochemical process, which is commonly carried out at 60–80 °C. For oxygen reduction and fuel oxidation to occur at such low temperatures platinum or platinum-alloy catalysts in the electrodes are required. To maximize the utilization of the noble metal it is frequently deposited as nanoparticles (1–5 nm) on a stabilizing support of carbon black. Carbon black provides good anchoring of the catalyst particles, but is prone to severe destructive oxidation at high electrical potentials encountered occasionally in fuel cells. Other nanostructures of carbon are being investigated as alternatives to carbon black as they have several beneficial properties. Multi-walled carbon nanotubes (MW-CNT) are an example of one type of these promising materials. Like carbon black they can conduct electrons to and from the reaction sites, and in addition their resistance to electrochemical degradation is better than that of carbon black due to their much higher structural perfection. This latter feature is indeed highly desired with a view to the durability of the fuel-cell electrodes. However, the low concentration of structural defects also poses challenges with regard to anchoring of the catalyst particles on the CNT surface. Thus, activation treatments introducing surface functional groups may be necessary. Also, the surface properties are responsible for difficulties in contacting the nanotubes with other substances in the electrode or electrode preparation. Other promising candidate structures for catalyst support include carbon nanofibers (CNF) and various modifications of CNTs. We present some of our work with the investigation of surface properties that are relevant for the preparation of fuel-cell electrodes with increased durability. This includes adsorption studies and studies of the role of the surface structure in the generation of materials-deteriorating reaction intermediates during the electrocatalytic processes.