Histone acetylation and deacetylation can be dynamically regulated in response to environmental stimuli and play important roles in learning and memory. Pharmacological inhibition of histone deacetylases (HDACs) improves performance in learning tasks; however, many of these classical agents are “pan-HDAC” inhibitors, and their use makes it difficult to determine the roles of specific HDACs in cognitive function. We took a genetic approach using mice lacking the class I HDACs, HDAC1 or HDAC2, in postmitotic forebrain neurons to investigate the specificity or functional redundancy of these HDACs in learning and synaptic plasticity. We show that selective knock-out of Hdac2 led to a robust acceleration of the extinction rate of conditioned fear responses and a conditioned taste aversion as well as enhanced performance in an attentional set-shifting task. Hdac2 knock-out had no impact on episodic memory or motor learning, suggesting that the effects are task-dependent, with the predominant impact of HDAC2 inhibition being an enhancement in an animal's ability to rapidly adapt its behavioral strategy as a result of changes in associative contingencies. Our results demonstrate that the loss of HDAC2 improves associative learning, with no effect in nonassociative learning tasks, suggesting a specific role for HDAC2 in particular types of learning. HDAC2 may be an intriguing target for cognitive and psychiatric disorders that are characterized by an inability to inhibit behavioral responsiveness to maladaptive or no longer relevant associations.