We suggest a specific new class of low-frequency g-modes in superfluid neutron stars. We determine the Brunt-Vaisala frequency for these modes and demonstrate that they can be unstable with respect to convection. The criterion for the instability onset (analogue of the well known Schwarzschild criterion) is derived. It is very sensitive to equation of state and a model of nucleon superfluidity. In particular, convection may occur for both positive and negative temperature gradients. Our results have interesting implications for neutron star cooling and seismology.