Pt-195 NMR spectroscopic and electrochemical measurements were carried out on commercial Pt-Ru alloy nanoparticle samples to investigate the effect of high-temperature annealing in different vacuum/gas -phase environments. Samples annealed at 220 degrees C in Ar gas, or in a vacuum, did not show any demonstrable change in catalytic activity vs electrochemically reduced, room-temperature samples. In contrast, annealing at 220 degrees C in H-2 gas led to a 3-fold increase in reactivity toward methanol oxidation (per surface site). NMR experiments show that annealing at 220 degrees C (in both Ar and H-2) leads to a slight reduction in the Fermi level local density of states (E-F-LDOS) at the Pt sites, which we attribute to surface enrichment of Ru. This electronic effect alone, however, appears to be too small to account for the increase in the catalytic activity observed for the H-treated catalyst. By comparing the electrochemical and NMR data of the H- and Ar-treated samples, we conclude that annealing at 220 degrees C in the hydrogen atmosphere reduces surface Ru oxides into metallic Ru, and consequently, the presence of metallic Ru and its enrichment on the surface are essential for the enhanced catalytic activity. In contrast, heat treatment at 600 degrees C in both vacuum and argon atmosphere increases the particle size and reduces the amount of platinum on the nanoparticle surface, thereby increasing the surface Ru content beyond the optimum surface composition values. This causes a large reduction in catalytic activity. Our results suggest that optimizing the amount of surface Ru by heat treatment at temperatures near 200 degrees C, in a hydrogen atmosphere, can be utilized to produce Pt-Ru alloy nanoparticles with high methanol oxidation activity. Finally, our NMR and electrochemical data, taken together with the lattice parameter measurements, lead to a novel model of Pt-Ru alloy nanoparticles having a Ru-rich core and a Pt-Ru alloy overlayer.