Memory consolidation requires a timely controlled interplay between the hippocampus, a brain region important for memory formation, and the cortex, a region recruited for memory storage. Here we show that memory consolidation is associated with specific epigenetic modifications on histone proteins that have a distinct dynamic in these brain areas. While in the hippocampus, histone post-translational modifications (PTMs) are rapidly and transiently activated after learning, in the cortex they are induced with delay but persist over time. When these histone PTMs are increased in vivo by transgenic intervention or intense training, they facilitate memory consolidation. Conversely, when they are pharmacologically blocked, memory consolidation is impaired. These histone PTMs are further associated with the expression of the immediate early gene zif268, a transcription factor that favours memory consolidation. These findings reveal the spatiotemporal dynamics of histone marks during memory consolidation, and demonstrate their inherent 'mnemonic' property.