Phenolic compounds constitute a sizable fraction of depolymerized biomass and are an ideal feedstock for the production of chemicals such as benzene and toluene. However, these compounds require catalytic upgrade via hydrodeoxygenation (HDO), a process whereby oxygen is removed as water by adding hydrogen while retaining the carbon molecular architecture. While the HDO of phenolics has been widely studied, a mechanism that is consistent with the data is still lacking. Herein, we perform first-principles microkinetic calculations for the HDO mechanism of an archetypical compound, p-cresol, on Pt(111). In contrast to the general belief, and in accordance with experimental data, we show that the single metal functionality is sufficient to carry out the HDO chemistry selectively, although ring activation is necessary. However, complete hydrogenation of the ring is neither necessary nor kinetically preferred. As a result, the conversion of p-cresol to toluene follows a complex energy landscape, where methylcyclohexanol and methylcyclohexane are not intermediates to toluene but rather share a common pool of intermediates with the hydrocarbons.