The neural mechanisms underlying behavioral flexibility are linked to the prefrontal cortex-basal ganglia circuit. Particularly, the flexibility is mediated through the dorsomedial striatum (DMS). To address the role of cholinergic interneurons in the DMS in behavioral flexibility, we conducted the selective elimination of cholinergic interneurons in rats by the immunotoxin-mediated cell targeting. Elimination of cholinergic interneurons in the DMS, but in dorsolateral striatum, resulted in the amelioration of reversal/extinction learning, sparing the acquisition of original place learning. This enhancement was reversed by the infusion of non-selective muscarinic receptor agonist into the DMS, either during the acquisition or reversal/extinction learning. Furthermore, the gene silencing of M₁ or M₄ muscarinic receptor in the DMS was conducted by lentiviral expression of short hairpin RNA. M₄ receptor knockdown mimicked the enhancement of reversal learning shown by the cholinergic elimination, but M₁ receptor knockdown did not. Our data provide the evidence that the cholinergic interneurons in the DMS are involved in the inhibition of behavioral flexibility, mainly through the M₄ muscarinic receptor.