We study the dynamics of a quantum system whose interaction with an environment is described by a collision model, i.e. the open dynamics is modelled through sequences of unitary interactions between the system and the individual constituents of the environment, termed ancillas, which are subsequently traced out. In this setting non-Markovianity is introduced by allowing for additional unitary interactions between the ancillas. For this model, we identify the relevant system-environment correlations that lead to a non-Markovian evolution. Through an equivalent picture of the open dynamics, we introduce the notion of memory depth where these correlations are established between the system and a suitably sized memory rendering the overall system+memory evolution Markovian. We extend our analysis to show that while most system-environment correlations are irrelevant for the dynamical characterization of the process, they generally play an important role in the thermodynamic description. Finally, we show that under an energy-preserving system-environment interaction, a non-monotonic time behaviour of the heat flux serves as an indicator of non-Markovian behaviour.