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\text{\,}\text{\,}\mathrm{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.