Cosmic-rays with energies exceeding 10^{19} eV are referred to as Ultra High Energy Cosmic Rays (UHECRs). The sources of these particles and their acceleration mechanism are unknown, and for many years have been the issue of much debate. The first part of this review describes the main constraints, that are implied by UHECR observations on the properties of candidate UHECR sources, the candidate sources, and the related main open questions. In order to address the challenges of identifying the UHECR sources and of probing the physical mechanisms driving them, a "multi-messenger" approach will most likely be required, combining electromagnetic, cosmic-ray and neutrino observations. The second part of the review is devoted to a discussion of high energy neutrino astronomy. It is shown that detectors, which are currently under construction, are expected to reach the effective mass required for the detection of high energy extra-Galactic neutrino sources, and may therefore play a key role in the near future in resolving the main open questions. The detection of high energy neutrinos from extra-Galactic sources will not only provide constraints on the identity and underlying physics of UHECR sources, but may furthermore provide information on fundamental neutrino properties.

16 pages, 10 figures; To be published in {\guillemotleft} Astronomy at the Frontiers of Science {\guillemotright}, ed. J.-P. Lasota, Springer 2011. The original publication will be available at http://www.springerlink.com