The graphene oxide-poly (p-phenylene diamine) (GP) composite is synthesized through in-situ polymerization of p-phenylene diamine on GO sheets and used as an efficient support material for electrodeposition of Ni and Mn. The resulting GP/Ni–Mn catalyst shows high catalytic activity, stability and durability for methanol electrooxidation. The surface area of GP composite is calculated to be about 28% and 36% higher than GO and PpPDA, respectively. In addition, combining Ni and Mn demonstrated some synergetic effect for methanol electrooxidation. The electrochemical active surface area of GP/Ni–Mn is about 1.625 cm2, which is much higher than GP/Ni and GP/Mn. GP/Ni–Mn nanocomposite presented 87.3% of the peak current after 5 h and almost 83.16% of the maximum current for 500 cycles. The excellent characteristics of this composite are attributed to high surface area, high electrochemical active surface area and fine distribution of metallic particles on the support material.