Nanoscale alloying constitutes an increasingly-important pathway for design of catalysts for a wide range of technologically important reactions. A key challenge is the ability to control the surface catalytic sites in terms of the alloying composition, thermochemical treatment and phase in correlation with the catalytic properties. Herein we show novel findings of the nanoscale evolution of surface catalytic sites on thermochemically-tuned gold-palladium nanoalloys by probing CO adsorption and oxidation using in situ diffuse reflectance infrared Fourier transform spectroscopy (DRIFTS) technique. In addition to the bimetallic composition and the support, the surface sites are shown to depend strongly on the thermochemical treatment condition, demonstrating that the ratio of three-fold vs. bridge or atop Pd sites is greatly reduced by thermochemical treatment under hydrogen in comparison with that under oxygen. This type of surface reconstruction is further supported by synchrotron high-energy X-ray diffraction coupled to atomic pair distribution function (HE-XRD/PDF) analysis of the nanoalloy structure, revealing an enhanced degree of random alloying for the catalysts thermochemically treated under hydrogen. The nanoscale alloying and surface site evolution characteristics were found to correlate strongly with the catalytic activity of CO oxidation. These findings have significant implications for the nanoalloy-based design of catalytic synergy.