Cognitive flexibility can be studied using the task-switching paradigm. This paradigm requires subjects to adapt behaviour to changing contexts as indicated by a cue. In our study, we addressed the question of how cue-based implementation of mental “task sets” occurs. We assumed that cues build up associations to the tasks that they indicate. These associations lead to retrieval of the associated task set once the cue shows up again. In three experiments, we tested this assumption using a negative transfer paradigm. First participants were exposed to one cue–task mapping. After a training phase, the cue–task mapping changed in either of two ways. Whereas one group of participants got new cues, the other experienced a reversal of the learnt cue–task mapping. Our results show that participants build up cue–task associations and that these formerly learnt associations can hamper the implementation of new cue–task mappings (particular with mapping reversal). Prolonged preparation time decreased the cost of changing the cue–task mapping but did not change the overall pattern of results.