The Standard Model of particle physics and General Relativity are expected to merge into a new theory of Quantum Gravity (QG) at energies approaching the Planck scale. However, none of the proposed QG approaches has been validated to date. In this context, several signatures of QG effects in accessible energy regimes, known as “Windows on Quantum Gravity”, have been postulated. In particular, quantum decoherence (QD) or QG-induced violation of Lorentz invariance (LIV), could cause modifications in neutrino oscillation patterns accessible to observation with neutrino telescopes. Moreover, the phenomenon of QD will provide new possibilities to investigate the neutrino nature as a Dirac or Majorana particle, as well as to trace possible violations of CPT symmetry in neutrino oscillations. Such a phenomenon represents a totally new scenario where to test the real nature of neutrinos. This talk reviews the efforts made in neutrino physics to search for QD and LIV effects and their implications in terms of QG models.