Daily living often requires individuals to flexibly respond to new circumstances. There is considerable evidence that the striatum is part of a larger neural network that supports flexible adaptations. Cholinergic interneurons are situated to strongly influence striatal output patterns which may enable flexible adaptations. The present experiments investigated whether acetylcholine actions in different striatal regions support behavioral flexibility by measuring acetylcholine efflux during place reversal learning. Acetylcholine efflux selectively increased in the dorsomedial striatum, but not dorsolateral or ventromedial striatum during place reversal learning. In order to modulate the M2-class of autoreceptors, administration of oxotremorine sesquifumurate (100 nM) into the dorsomedial striatum, concomitantly impaired reversal learning and an increase in acetylcholine output. These effects were reversed by the m(2) muscarinic receptor antagonist, AF-DX-116 (20 nM). The effects of oxotremorine sesquifumurate and AF-DX-116 on acetylcholine efflux were selective to behaviorally-induced changes as neither treatment affected acetylcholine output in a resting condition. In contrast to reversal learning, acetylcholine efflux in the dorsomedial striatum did not change during place acquisition. The results reveal an essential role for cholinergic activity and define its locus of control to the dorsomedial striatum in cognitive flexibility.