The natural framework to discuss thermodynamics at the quantum level is the theory of open quantum systems. Memory effects arising from strong system-environment correlations may lead to information back-flow, that is non-Markovian behaviour. The relation between non-Markovianity and quantum thermodynamics has been until now largely unexplored. Here we show by means of Landauer's principle that memory effects control the amount of work extraction by erasure in presence of realistic environments.