The presence of a capping agent (CTAB) on Pd nanoparticles produces a strong static disorder in the surface region. This results in a surface softening, which contributes to an overall increase in the Debye-Waller coefficient measured by X-ray powder diffraction. Molecular dynamics and density functional theory simulations show that the adsorption-induced surface disorder is strong enough to overcome the effects of nanoparticle size and shape.