Using the paradigm of information backflow to characterize a non-Markovian evolution, we introduce so-called precursors of non-Markovianity, i.e. necessary properties that the system and environment state must exhibit at earlier times in order for an ensuing dynamics to be non-Markovian. In particular, we consider a quantitative framework to assess the role that established system-environment correlations together with changes in environmental states play in an emerging non-Markovian dynamics. By defining the relevant contributions in terms of the Bures distance, which is conveniently expressed by means of the quantum state fidelity, these quantities are well defined and easily applicable to a wide range of physical settings. We exemplify this by studying our precursors of non-Markovianity in discrete and continuous variable non-Markovian collision models.