In the standard model neutrinos are assumed to have streamed across the Universe since they last scattered at the weak decoupling epoch when the temperature of the standard-model plasma was ~MeV. The shear stress of free-streaming neutrinos imprints itself gravitationally on the Cosmic Microwave Background (CMB) and makes the CMB a sensitive probe of neutrino scattering. Yet, the presence of nonstandard physics in the neutrino sector may alter this standard chronology and delay neutrino free-streaming until a much later epoch. We will discuss how observations of the CMB can be used to constrain the strength of neutrino self-interactions G_eff and put limits on new physics in the neutrino sector from the early Universe. Key measurements of the CMB at large multipoles made by the Planck satellite and high-l experiments are critical for probing this physics. Within the context of conventional LambdaCDM parameters cosmological data are compatible with G_eff < 1/(56 MeV)^2 and neutrino free-streaming might be delayed until their temperature has cooled to as low as ~25 eV. Intriguingly, we also find an alternative cosmology compatible with cosmological data in which neutrinos scatter off each other until z~10^4 with a preferred interaction strength in a narrow region around G_eff = 1/(10 MeV)^2. This distinct self-interacting neutrino cosmology is characterized by somewhat lower values of both the scalar spectral index and the amplitude of primordial fluctuations. We phrase our discussion in terms of a specific scenario in which a late onset of neutrino free-streaming could occur, but in fact our constraints on the neutrino visibility function are very general.