We show that the combination of cross-phase modulation and polarization-mode dispersion inside optical fibers leads to a novel phenomenon of intrapulse depolarization manifested as different random states of polarization across the pulse profile. Such polarization evolution of optical pulses is directly analogous to the phenomenon of spin decoherence in semiconductors or pseudospin relaxation in atoms.