A universal definition of non-Markovianity for open systems dynamics is proposed. It is extended from the classical definition to the quantum realm by showing that a `transition from the Markov to the non-Markov regime occurs when the correlations between the system and the environment, generated by their joint evolution, can no longer be neglected. The suggested definition is based on the comparison between measured correlation functions and those built by assuming that the system is in a Markov regime thus giving a figure of merit of the error coming from this assumption. It is shown that the knowledge of the dynamical map and initial condition of the system is not enough to fully characterise the non-Markovian dynamics of the reduced system. The example of three exactly solvable models, i.e. decoherence and spontaneous emission of the qubit in a bosonic bath and decoherence of the photons polarization induced by interaction with its spacial degrees of freedom, reveals that previously proposed Markovianity criteria and measures which are based on dynamical map analysis fail to recognise non-Markov behaviour.