Faraday rotation (RM) probes of magnetic fields in the universe are sensitive to cosmological and evolutionary effects as $z$ increases beyond $\sim $1 because of the scalings of electron density and magnetic fields, and the growth in the number of expected intersections with galaxy-scale intervenors, $d$N/$dz$. In this new global analysis of an unprecedented large sample of RM's of high latitude quasars extending out to $z\sim $3.7 we find that the distribution of RM broadens with redshift in the 20 $-$ 80 rad m$^{-2}$ range range, despite the (1 +$z$)$^{-2}$ wavelength dilution expected in the observed Faraday rotation. Our results indicate that the Universe becomes increasingly ``Faraday-opaque'' to sources beyond $z \sim$ 2, that is, as $z$ increases progressively fewer sources are found with a ``small'' RM in the observer's frame. This is in contrast to sources at $z \la$1. They suggest that the environments of galaxies were significantly magnetized at high redshifts, with magnetic field strengths that were at least as strong within a few Gyr of the Big Bang as at the current epoch. We separately investigate a simple unevolving toy model in which the RM is produced by MgII absorber systems, and find that it can approximately reproduce the observed trend with redshift. An additional possibility is that the intrinsic RM associated with the radio sources was much higher in the past, and we show that this is not a trivial consequence of the higher radio luminosities of the high redshift sources.