Catalysts containing Pt nanoparticles and reducible transition-metal oxides (WOx, NbOx, TiOx) exhibit remarkable selectivity to aromatic products in hydrodeoxygenation (HDO) reactions for biomass valorization, contrasting the undesired aromatic hydrogenation typically observed for metal catalysts. However, the active site(s) responsible for the high selectivity remains elusive. Here, theoretical and experimental analyses are combined to explain the observed HDO reactivity by interrogating the organization of reduced WOxdomains on Pt surfaces at sub-monolayer coverage. The SurfGraph algorithm is used to develop model structures that capture the configurational space (∼1000 configurations) for density functional theory (DFT) calculations of a W3O7trimer on stepped Pt surfaces. Machine-learning models trained on the DFT calculations identify the preferential occupation of well-coordinated Pt sites (≥8 Pt coordination number) by WOxand structural features governing WOx–Pt stability. WOx/Pt/SiO2catalysts are synthesized with varying W loadings to test the theoretical predictions and relate them to HDO reactivity. Spectroscopy- and microscopy-based catalyst characterizations identify the dynamic and preferential decoration of well-coordinated sites on Pt nanoparticles by reduced WOxspecies, consistent with theoretical predictions. The catalytic consequences of this preferential decoration on the HDO of a lignin model compound, dihydroeugenol, are clarified. The effect of WOxdecoration on Pt nanoparticles for HDO involves WOxinhibition of aromatic ring hydrogenation by preferentially blocking well-coordinated Pt sites. The identification of preferential decoration on specific sites of late-transition-metal surfaces by reducible metal oxides provides a new perspective for understanding and controlling metal–support interactions in heterogeneous catalysis.