We estimate the depolarizing effect of a primordial magnetic field upon the cosmic microwave background radiation due to differential Faraday rotation across the last scattering surface. The degree of linear polarization of the CMB is significantly reduced at frequencies around and below 30 GHz $(B_* /10^{-2}{\rm Gauss})^{1/2}$, where $B_*$ is the value of the primordial field at recombination. The depolarizing mechanism reduces the damping of anisotropies due to photon diffusion on small angular scales. The $l\approx 1000$ multipoles of the CMB temperature anisotropy correlation function in a standard cold dark matter cosmology increase by up to 7.5\% at frequencies where depolarization is significant.