We have studied the femtosecond dynamics following optical laser excitation of CO adsorbed on a Ru surface by monitoring changes in the occupied and unoccupied electronic structure using ultrafast soft x-ray absorption and emission. We recently reported [M. Dell'Angela et al. Science 339, 1302 (2013)] a phonon-mediated transition into a weakly adsorbed precursor state occurring on a time scale of >2 ps prior to desorption. Here we focus on processes within the first picosecond after laser excitation and show that the metal-adsorbate coordination is initially increased due to hot-electron-driven vibrational excitations. This process is faster than, but occurs in parallel with, the transition into the precursor state. With resonant x-ray emission spectroscopy, we probe each of these states selectively and determine the respective transient populations depending on optical laser fluence. Ab initio molecular dynamics simulations of CO adsorbed on Ru(0001) were performed at 1500 and 3000 K providing insight into the desorption process.