Abstract: We explore in a rigorous manner the intuitive connection between the non-Markovianity of the evolution of an open quantum system and the performance of the system as a quantum memory. Using the paradigmatic case of a two-level open quantum system coupled to a bosonic bath, we compute the recovery fidelity, which measures the best possible performance of the system to store a qubit of information. We deduce that this quantity is connected, but not uniquely determined, by the non-Markovianity, for which we adopt the Breuer-Laine-Piilo measure proposed in Breuer et al (2009 Phys. Rev. Lett. 103 210401). We illustrate our findings with explicit calculations for the case of a structured environment.