We review the peculiarities that make neutrinos very special cosmic messengers in high-energy astrophysics, and, in particular, to provide possible indications of deviations from special relativity, as it is suggested theoretically by quantum gravity models. In this respect, we examine the effects that one could expect in the production, propagation, and detection of neutrinos, not only in the well-studied scenario of Lorentz Invariance Violation, but also in models which maintain, but deform, the relativity principle, such as those considered in the framework of Doubly Special Relativity. We discuss the challenges and the promising future prospects offered by this phenomenological window to physics beyond special relativity.