Memory is not a faithful recording of sensory experience. Rather, a century of research has shown memories are prone to systematic distortions through interpretation, selective encoding and subsequent modifications. Recent applications of Rate Distortion Theory (RDT) offer a normative framework for understanding memory encoding as lossy compression, accounting for a range of phenomena such as gist-based distortions. However, RDT assumes the statistics of the environment are static and known—a stark contrast to the brain’s continual need to update its internal (semantic) model of the world. We propose an extension of RDT where the compression model is itself learned from experience, creating a dynamic interplay between compression and learning, which in turn induces characteristic path-dependencies in learning. By reinterpreting previous empirical findings in the light of this proposal, our approach broadens the explanatory scope of RDT to a wider range of memory phenomena such as associative memory errors and post-event misinformation.