Extragalactic sources are believed to dominate the ultra-high energy cosmic ray (CR) spectrum beyond the CR "knee". These sources are also expected to produce very high-energy neutrinos via interactions with gas and radiation during acceleration and emission of CRs or during CR propagation over cosmic distances. I will focus in my talk on extragalactic source candidates of the TeV-PeV neutrino flux recently observed by the IceCube Cherenkov telescope. There are various interesting multi-messenger relations to gamma-rays and cosmic rays. The TeV-PeV gamma-rays produced in hadronic interactions are not directly accessible by extragalactic gamma-ray astronomy due to interactions with cosmic radiation backgrounds. Nevertheless, the isotropic sub-TeV gamma-ray background observed by Fermi-LAT contains indirect information from secondary emission produced in electromagnetic cascades and constrains hadronic emission scenarios. Interestingly, the overall energy density of the observed neutrino flux is close to a theoretical limit for neutrino production in the sources of ultra-high energy cosmic rays and might indicate a common origin of these phenomena. I will discuss various constraints and implications of these multi-messenger relations for proposed source candidates.