A simple relationship between recently proposed measures of non-Markovianity and the Loschmidt echo is established, holding for a two-level system (qubit) undergoing pure dephasing due to a coupling with a many-body environment. We show that the Loschmidt echo is intimately related to the information flowing out from and occasionally back into the system. This, in turn, determines the non-Markovianity of the reduced dynamics. In particular, we consider a central qubit coupled to a quantum Ising ring in the transverse field. In this context, the information flux between system and environment is strongly affected by the environmental criticality; the qubit dynamics is shown to be Markovian exactly and only at the critical point. Therefore non-Markovianity is an indicator of criticality in the model considered here.