Stochastic backgrounds of gravitational waves are intrinsic fluctuations of spacetime which lead to an unavoidable decoherence mechanism. This mechanism manifests itself as a degradation of the contrast of quantum interferences. It defines an ultimate decoherence border for matter-wave interferometry using larger and larger molecules. We give a quantitative characterization of this border in terms of figures involving the gravitational environment as well as the sensitivity of the interferometer to gravitational waves. The known level of gravitational noise determines the maximal size of the molecular probe for which interferences may remain observable. We discuss the relevance of this result in the context of ongoing progresses towards more and more sensitive matter-wave interferometry.