Secondary photons and neutrinos produced in the interactions of cosmic ray protons emitted by distant Active Galactic Nuclei (AGN) with the photon background along the line of sight can reveal a wealth of new information about the intergalactic magnetic fields (IGMF), extragalactic background light (EBL), and the acceleration mechanisms of cosmic rays. The secondary photons may have already been observed by gamma-ray telescopes. We show that the secondary neutrinos improve the prospects of discovering distant blazars by IceCube, and we discuss the ramifications for the cosmic backgrounds, magnetic fields, and AGN models. ; Comment: 4 pages, 2 figures; final version accepted for publication in PRL