To greatly improve the electrocatalytic activity for methanol oxidation, high-quality exfoliated graphene decorated with uniform Pt nanocrystals (NCs) (3 nm) have been prepared by a very simple, low-cost and environmentally benign process. During the entire process, no surfactant and no halide ions were involved, which not only enabled very clean surface of Pt/graphene leading to excellent conductivity, but also greatly improved the electrocatalyst tolerance to carbon monoxide poisoning (Pt/graphene, If/Ib = 1.197), compared to commercial Pt/C (If/Ib = 0.893) catalysts. To maximize the electrocatalytic performance and minimize the amount of precious Pt, Pt–M/graphene (M = Pd, Co) hybrids have also been prepared, and these hybrids have much larger electrochemically active surface areas (ECSA), which are 4 (PtPd/graphene) and 3.3 (PtCo/graphene) times those of commercial Pt/C. The PtPd/graphene and PtCo/graphene hybrids also have remarkably increased activity toward methanol oxidation (If/Ib = 1.218 and 1.558). Furthermore, density functional theory (DFT) simulations demonstrate that an electronic interaction occurred between Pt atoms and graphene, indicating that graphene substrate plays a crucial role in regulating the electron structure of attached Pt atom, which confirmed that the increased efficiency of methanol oxidation was due to the synergetic effects of the hybrid structure.