Platinum and the metal M were co-sputtered from separate cathode targets simultaneously using a high-voltage direct current on a Toray paper substrate. The atomic composition of metal M to platinum was varied between 0.1-2 by fixing the sputtering power to the platinum target and varying the sputtering power to the target containing metal M. The structure, morphology and composition of the catalyst were investigated by SEM, EDX and XPS. The results of quasi-steady state voltammetry suggested that the well-known bi-functional mechanism for methanol oxidation was operative on Pt-Nb and Pt-Ta catalysts. With the same amount of platinum, the methanol oxidation current of Pt-Ta and Pt-Nb catalyst was significantly improved compared to a sputtered platinum catalyst (Figure 1). The methanol oxidation current of Pt-Ta and Pt-Nb catalyst was 11.1 times and 8.3 times of platinum catalyst at -0.1 V vs. mercury/mercury sulfate reference electrode. We will present our understanding of the interaction between Pt and M (M=Nb, Ta) in enhancing the electro-oxidation of methanol and report on our efforts towards optimization of the catalyst composition to lower the noble metal content and enable practical use of these new catalyst materials in fuel cells