The detection of high energy extra-terrestrial neutrinos by IceCube opens a new window for observations of the Universe. I will discuss the likely extra-Galactic origin of these neutrinos, the clues that their detection provides towards the solution of the long standing question of the origin of cosmic-rays (CRs), and the prospects for identifying the CR sources and for studying open questions in particle physics and astrophysics using combined electromagnetic and neutrino observations.