In the present work, methanol oxidation reaction was investigated on Pt particles of various diameters on carbon-nanofibers and carbon-black supports with different surface-oxygen concentrations, aiming for a better understanding of the relationship between the catalyst properties and the electrochemical performance. The pre-synthesized Pt nanoparticles in ethylene glycol, prepared by the polyol method without using any capping agents, were deposited on different carbon supports. Removal of oxygen-groups from the carbon supports had profound positive effects on not only the Pt dispersion but also the specific activity. The edge structures on the stacked graphene sheets in the platelet carbon-nanofibers provided a strong interaction with the Pt particles, significantly reconstructing them in the process. Such reconstruction resulted in the formation of more plated Pt particles on the CNF than on the carbon-black and exposure of more Pt atoms with relatively high co-ordination numbers, and thereby higher specific activity. Owing to the combined advantages of optimum Pt particle diameter, an oxygen-free surface and the unique properties of CNFs, Pt supported on heat-treated CNFs exhibited a higher mass activity twice of that of its commercial counterpart.