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 WOx domains 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 W3O7 trimer 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 WOx and structural features governing WOx-Pt stability. WOx/Pt/SiO2 catalysts 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 WOx species, 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 WOx decoration on Pt nanoparticles for HDO involves WOx inhibition 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.