We address the problem of quantifying the non-Markovian character of quantum time-evolutions of general systems in contact with an environment. We introduce two different measures of non-Markovianity that exploit the specific traits of quantum correlations and are suitable for opposite experimental contexts. When complete tomographic knowledge about the evolution is available, our measure provides a necessary and sufficient condition to quantify strictly the non-Markovianity. In the opposite case, when no information whatsoever is available, we propose a sufficient condition for non-Markovianity. Remarkably, no optimization procedure underlies our derivation, which greatly enhances the practical relevance of the proposed criteria.