Ceria-supported palladium (Pd/CeO2) has spawned significant attention in recent years due to its ability to catalyze selective hydrogenation of phenolic compounds to cyclohexanones and cyclohexanols at a mild temperature and pressure. However, the mechanistic basis by which ceria enhances catalytic conversion is still unclear. Here, we use the increase in the 13C transverse relaxation rate upon the addition of nanoparticles (NPs) (13C ΔR2) to investigate the adsorption of phenolic compounds on the surface of the Pd/CeO2 catalyst by solution NMR. We show that hydroxyphenols adsorb on the support more efficiently than underivatized phenol and methoxyphenols and that phenol derivatives with an oxygen atom at position 2 (i.e., 2-hydroxyphenol and 2-methoxyphenol) form very stable interactions with the Pd site of Pd/CeO2. An analysis of the kinetics of hydrogenation revealed that catalytic conversion is linearly correlated with the ability of the substrate to form interactions with the CeO2 support and is inhibited by the formation of stable substrate–Pd adducts. Our data suggest that CeO2–substrate interactions mediate phenol hydrogenation more efficiently than Pd–substrate interactions and explain the exceptional catalytic performance reported for Pd/CeO2.