Multiple studies have found that increasing histone acetylation by means of histone deacetylase inhibitor (HDACi) treatment can ameliorate memory and rescue cognitive impairments, but their mode of action is not fully understood. In particular, it is unclear how HDACis, applied systemically and devoid of genomic target selectivity, would specifically improve memory-related molecular processes. One theory for such specificity is called cognitive epigenetic priming (CEP), according to which HDACis promote memory by facilitating the expression of neuroplasticity-related genes that have been stimulated by learning itself. In this review, we summarize the experimental evidence in support of CEP, describe newly discovered off-target effects of HDACis and highlight similarities between drug-induced and naturally occurring CEP. Understanding the underlying mechanisms of CEP is important in light of the preclinical premise of HDACis as cognitive enhancers.