Solvent molecules influence the reactions of molecular hydrogen and oxygen on palladium nanoparticles. Organic solvents activate to form reactive surface intermediates that mediate oxygen reduction through pathways distinct from reactions in pure water. Kinetic measurements and ab initio quantum chemical calculations indicate that methanol and water cocatalyze oxygen reduction by facilitating proton-electron transfer reactions. Methanol generates hydroxymethyl intermediates on palladium surfaces that efficiently transfer protons and electrons to oxygen to form hydrogen peroxide and formaldehyde. Formaldehyde subsequently oxidizes hydrogen to regenerate hydroxymethyl. Water, on the other hand, heterolytically oxidizes hydrogen to produce hydronium ions and electrons that reduce oxygen. These findings suggest that reactions of solvent molecules at solid-liquid interfaces can generate redox mediators in situ and provide opportunities to substantially increase rates and selectivities for catalytic reactions.