Graphene-supported PtPd alloy nanocubes (PtPd/RGO) were synthesized via a facile and versatile one-pot hydrothermal synthetic strategy, which proved to be a universal technique for preparing other graphene-supported alloy nanocrystals. In acidic electrolyte, the PtPd/RGO composites exhibited much enhanced electrocatalytic activity toward methanol oxidation compared to the unsupported PtPd alloy nanocubes with a similar size and shape, and the commercial Pt/C catalyst. More interestingly, we found that CO stripping is an efficient method to remove the surfactants wrapped on the particle surface and thus enhance the electrocatalytic performance of the Pt-based nanocrystals. After CO stripping treatment, the PtPd/RGO composites exhibited a much more negative onset potential of methanol oxidation than those of the unsupported PtPd alloy nanocubes and the commercial Pt/C catalyst. Moreover, the treated PtPd/RGO displayed a mass-specific methanol oxidation activity of 198 mA/mg Metal at 0.62 V (vs Ag/AgCl), nearly 3.14 times higher than those of the unsupported PtPd alloy nanocubes (63 mA/mgMetal) and the commercial Pt/C catalyst (64 mA/mgMetal). On the other hand, the PtPd/RGO exhibited much higher stability during the methanol electrooxidation with almost no loss of the electrochemical active surface area (ECSA) and activity after 1000 electrochemical cycles. On the contrary, the unsupported PtPd nanocubes and the commercial Pt/C catalyst lost 8.5% and 25.7% of their initial ECSA, and 6.2% and 20.6% of the initial peak current after 1000 cycles of methanol oxidation reaction. The excellent stability of the PtPd/RGO can also be reflected from the fact that the morphology, size, and dispersity of the PtPd nanocubes exhibited no significant change after 1000 potential cycles.