The ability to change strategies in different contexts is a form of behavioral flexibility that is crucial for adaptive behavior. The striatum has been shown to contribute to certain forms of behavioral flexibility such as reversal learning. Here we report on the contribution of striatal cholinergic interneurons—a key element in the striatal neuronal circuit—to strategy set-shifting in which an attentional shift from one stimulus dimension to another is required. We made lesions of rat cholinergic interneurons in dorsomedial or ventral striatum using a specific immunotoxin and investigated the effects on set-shifting paradigms and on reversal learning. In shifting to a set that required attention to a previously irrelevant cue, lesions of dorsomedial striatum significantly increased the number of perseverative errors. In this condition, the number of never-reinforced errors was significantly decreased in both types of lesions. When shifting to a set that required attention to a novel cue, rats with ventral striatum lesions made more perseverative errors. Neither lesion impaired learning of the initial response strategy nor a subsequent switch to a new strategy when response choice was indicated by a previously relevant cue. Reversal learning was not affected. These results suggest that in set-shifting the striatal cholinergic interneurons play a fundamental role, which is dissociable between dorsomedial and ventral striatum depending on behavioral context. We propose a common mechanism in which cholinergic interneurons inhibit neurons representing the old strategy and enhance plasticity underlying exploration of a new rule.