We show that coadsorbed oxygen atoms have a dramatic influence on the CO desorption dynamics from Ru(0001). In contrast to the precursor-mediated desorption mechanism on Ru(0001), the presence of surface oxygen modifies the electronic structure of Ru atoms such that CO desorption occurs predominantly via the direct pathway. This phenomenon is directly observed in an ultrafast pump-probe experiment using a soft x-ray free-electron laser to monitor the dynamic evolution of the valence electronic structure of the surface species. This is supported with the potential of mean force along the CO desorption path obtained from density-functional theory calculations. Charge density distribution and frozen-orbital analysis suggest that the oxygen-induced reduction of the Pauli repulsion, and consequent increase of the dative interaction between the CO 5σ and the charged Ru atom, is the electronic origin of the distinct desorption dynamics. Ab initio molecular dynamics simulations of CO desorption from Ru(0001) and oxygen-coadsorbed Ru(0001) provide further insights into the surface bond-breaking process.