We show that, contrary to general belief, g-modes can exist in superfluid neutron stars. Unlike ordinary composition g-modes in cold non-superfluid neutron stars, these g-modes turn out to be very temperature-dependent and can have frequencies up to ~0.5 kHz. We analyze their properties and briefly discuss the ways they can be excited. Possible observational signatures of the proposed g-modes are also examined. This work was partially supported by RF president programme (grants MK-506.2014.2), by RFBR (grants 11-02-00253-a and 14-02-31616-mol-a), by the Dynasty Foundation, and by the Ministry of Education and Science of Russian Federation (Agreement No.\ 8409, 2012).