The durability of a fuel cell having a polymer electrolyte membrane with an anode on one surface and an oxygen-reducing cathode on the other surface is improved by substituting electrically conductive titanium carbide or titanium nitride particles for carbon particles as oxygen-reducing and hydrogen-oxidizing catalyst supports. For example nanosize platinum particles deposited on nanosize titanium carbide or titanium nitride support particles provide good oxygen reduction capability and are corrosion resistant in an acid environment. It is preferred that the catalyst-on-titanium carbide (nitride) particles be mixed with non-catalyst-bearing carbon in the electrode material for improved electrode performance.