The dynamical behavior of image-potential states has been studied with two-photon photoemission for CO on Cu(100). The pure dephasing is observed as the loss of coherence in quantum beats, or derived from linewidth and lifetime measurements. A correlation to the surface order as observed by low-energy electron diffraction (LEED) is also established.