Atomic-scale calculations of stress induced by a transition metal adsorbate on a metal surface are presented. A newly developed many-body potential is used. We show that Co adatoms strongly reduce local surface stress and lead to an inhomogeneous stress distribution. Barriers of jump and exchange diffusion are determined for Co on Au(001). We predict that the exchange process is energetically favorable. Molecular dynamics calculations are performed to determine the coverage dependence of the adsorbate-induced surface stress.