- Strong intergalactic shocks are a natural consequence of structure formation in the universe. These shocks are expected to deposit large fractions of their thermal energy in relativistic electrons (ξe 0.05 according to supernova remnant observations) and magnetic fields (ξB 0.01 according to cluster halo observations). We calculate the synchrotron emission from such shocks using an analytical model, calibrated and verified based on a hydrodynamic ΛCDM simulation. The resulting signal composes a large fraction (up to a few 10%) of the extragalactic radio background below 500 MHz. The associated angular fluctuations, e.g., δTl 260(ξeξB/5 × 10-4)(ν/100 MHz)-3 K for multipoles 400 l 2000, dominate the radio sky for frequencies ν 10 GHz and angular scales 1' θ < 1° (after a modest removal of discrete sources), provided that ξeξB 3 × 10-4. The fluctuating signal is most pronounced for ν 500 MHz, dominating the sky there even for ξeξB = 5 × 10-5. The signal will be easily observable by next-generation telescopes such as the LOFAR and the SKA and is marginally observable with present-day radio telescopes. The signal could also be identified through a cross-correlation with tracers of large-scale structure (such as γ-ray emission from intergalactic shocks), possibly even in existing 10 GHz CMB anisotropy maps and high-resolution ~1 GHz radio surveys. Detection of the signal will provide the first identification of intergalactic shocks and of the warm-hot intergalactic medium (believed to contain most of the baryons in the low-redshift universe), and gauge the unknown strength of the intergalactic magnetic field. We analyze existing observations of the diffuse radio background below 500 MHz and show that they are well fitted by a simple, double-disk Galactic model, precluding a direct identification of the diffuse extragalactic radio background. Modeling the frequency-dependent anisotropy pattern observed at very low (1-10 MHz) frequencies can be used to disentangle the distributions of Galactic cosmic rays, ionized gas, and magnetic fields. Space missions such as the Astronomical Low Frequency Array will thus provide an important insight into the structure and composition of our Galaxy.