The variation of the work function upon carbon adsorption on the reconstructed Au(110) surface is measured experimentally and compared to density functional calculations. The adsorption dynamics is simulated with ab-initio molecular dynamics techniques. The contribution of various energetically available adsorption sites on the deposition process is analyzed, and the work function behavior with carbon coverage is explained by the resultant electron charge density distributions.