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.