We have re-analyzed the NRAO VLA Sky Survey (NVSS) data to derive rotation measures (RMs) toward 37,543 polarized radio sources. The resulting catalog of RM values covers the sky area north of declination -40° with an average density of more than one RM per square degree. We present an image of the median RM over 82% of the sky with a resolution of 8° and a typical error of ±1-2 rad/m2. The image shows large-scale structures in RM that extend to very high Galactic latitudes. A simple analysis of the RM structure at high Galactic latitudes is used to derive properties of the Galactic halo magnetic field in the solar neighborhood. We find the component of the local field perpendicular to the plane (the z-component) equal to +0.30 µG for z < 0 and -0.14 µG for z>0. The reversal of sign across the Galactic plane is consistent with a quadrupole field geometry for the poloidal component of the halo field. The halo magnetic field component parallel to the disk is also found to be antisymmetric and generally consistent with a toroidal field, with strength +0.83 µG for z < 0 and -0.39 µG for z>0. We have identified five regions of the sky where the foreground median RM is consistently less than 1 rad/m2 over several degrees. These holes in the foreground RM will be useful for future studies of possible small-scale fluctuations in cosmic magnetic field structures. In addition to allowing measurement of RMs toward polarized sources, the new analysis of the NVSS data removes the effects of bandwidth depolarization for|RM| ≳ 100 rad/m2 inherent in the original NVSS source catalog. This new catalog of RMs and polarized flux densities is available online, and will be a valuable resource for further studies of the Galactic magnetic field and magnetoionic medium, and extragalactic magnetic fields.