We report hexadecyltrimethylammonium bromide (CTAB)-functionalized graphene as a carbon support for Pt or PtCo nanoparticle (NP) catalysts for fuel cell cathodes. The CTAB treatment plays several critical roles in improving the cell performance: CTAB is non-covalently bound on the graphene surfaces and also functionalizes NP surfaces, thus minimizing aggregation between graphene sheets as well as between NPs with extremely small dimensions down to 1-2 nm for a large number of cycles. Also, unlike covalent bonding based treatments, the CTAB treatment preserves intrinsic electronic and structural properties of graphene. The increased dispersion and decreased dissolution of NP catalysts using the CTAB functionalization are reflected in various electrochemical measurements such that the CTAB-treated samples exhibit higher values in oxygen reduction reaction activity, electrochemical active surface area, and long-term durability compared to commercial catalysts and control cases with no such treatment. Finally, for the same CTAB-treated graphene, PtCo catalyst shows a higher catalytic activity than does Pt catalyst, thus confirming the known improved activities of the alloyed catalysts.