We have investigated the full reaction path leading to the formation of HCN from ammonia and methane on Pt(111) by means of density functional theory. Industrially, the reaction can take place under oxidative or nonoxidative conditions, and thus, we have described the effect of oxygen in the reaction mechanism. DFT calculations show that the reaction network is very complex, including dehydrogenation steps, H_xC-NH_y (x = 0-2, y = 0-2) couplings, de/hydrogenation of C-N-containing species, and isomerization. Under nonoxidative conditions (Degussa process), the main reaction path for C-N formation takes place through partially hydrogenated compounds, in particular, those coming from H_xC + NH₂ (x = 0, 1) coupling with subsequent dehydrogenation of the resulting intermediate. Under oxygen-rich conditions (Andrussow), the main C-N bond formation step switches to HC + N or C + N. The mechanistic switch between oxidative and nonoxidative conditions is driven by the change in the relative stability of the intermediates, induced by the presence of oxygen and the lack of free surface H atoms. Our calculations clarify previous observations where different mechanisms were described.