We propose the use of heralded photons to detect Gravitational Waves (GWs). Heralded photons are those photons that, produced during a parametric downconversion process, are "labelled" by the detection and counting of coincidences of their correlated or entangled twins and therefore can be discriminated from the background noise, independently of the type of correlation/entanglement used in the setup. Without losing any generality, we illustrate our proposal with a gedankenexperiment, in which the presence of a gravitational wave causes a relative rotation of the reference frames associated to the double-slit and the test polarizer, respectively, of a Walborn's quantum eraser \cite{wal02}. In this thought experiment, the GW is revealed by the detection of heralded photons in the dark fringes of the recovered interference pattern by the quantum eraser. Other types of entanglement, such as momentum-space or energy-time, could be used to obtain heralded photons to be used in the future with high-frequency GW interferometric detectors when enough bright sources of correlated photons will be available.