Cellular models of memory formation have focused on the need for protein synthesis. Recently, evidence has emerged that protein degradation mediated by the ubiquitin-proteasome system (UPS) is also important for this process. This has led to revised cellular models of memory formation that focus on a balance between protein degradation and synthesis. However, protein degradation is only one function of the UPS. Studies using single-celled organisms have shown that non-proteolytic ubiquitin-proteasome signaling is involved in histone modifications and DNA methylation, suggesting that ubiquitin and the proteasome can regulate chromatin remodeling independent of protein degradation. Despite this evidence, the idea that the UPS is more than a protein degradation pathway has not been examined in the context of memory formation. In this article, we summarize recent findings implicating protein degradation in memory formation and discuss various ways in which both ubiquitin signaling and the proteasome could act independently to regulate epigenetic-mediated transcriptional processes necessary for learning-dependent synaptic plasticity. We conclude by proposing comprehensive models of how non-proteolytic functions of the UPS could work in concert to control epigenetic regulation of the cellular memory consolidation process, which will serve as a framework for future studies examining the role of the UPS in memory formation.