Uncontrollability has been often associated with impaired or rigid cognitive processing. However, perceived stability of uncontrollable events modulated some of these detrimental effects on cognition. We investigated whether the experience of sequential control loss and restoration can enhance cognitive flexibility. We manipulated uncontrollability using a concept formation procedure that entailed either only unsolvable tasks (control deprivation condition), unsolvable tasks followed by solvable ones (control restoration condition) or only solvable tasks (control condition). To assess cognitive flexibility, we used a task-switching procedure that incorporated social categories. In Experiment 1 participants categorized people based on gender or age, and in Experiment 2 and 3 based on gender or social roles. Participants showed more flexibility in control restoration than in control deprivation condition. Additionally, in Experiments 2 and 3 this effect was mainly pronounced in the condition where the task evoked more cognitive conflict. We discuss the motivational underpinnings of unstable experiences of control loss and restoration.