We study the effect of Coulomb correlations on the ultrafast optical dynamics of small metal particles. We demonstrate that a surface-induced dynamical screening of the electron-electron interactions leads to quasiparticle scattering with collective surface excitations. In noble-metal nanoparticles, it results in an interband resonant scattering of d holes with surface plasmons. We show that this size-dependent many-body effect manifests itself in the differential absorption dynamics for frequencies close to the surface plasmon resonance. In particular, our self-consistent calculations reveal a strong frequency dependence of the relaxation, in agreement with recent femtosecond pump-probe experiments. © 1998 American Physical Society.