Humans can perform several different tasks on the same set of stimuli in rapid alternation. Each task, signaled by a distinct task cue, may require the classification of stimuli using a different stimulus attribute. However, such "task switching" performance comes at a cost, as expressed by weaker performance when switching rather than repeating tasks. This cost is often claimed to be the consequence of a mental reorientation away from the previous task and towards the new task, requiring executive control of behavior. Alternatively, task switching could simply be based on the retrieval of different cue-stimulus-response associations. In this experiment, pigeons learned go-left/go-right discriminations between grating patterns according to either their spatial frequency or their orientation, depending on the color of the pattern (the task cue). When humans solved the same tasks on the basis of verbalizable rules, they responded more slowly and made more errors on trials where they had to switch between tasks than when repeating the same task. Pigeons did not show this "switch cost"; but like humans, their performance was significantly worse when the response (left or right) to a given stimulus varied between tasks than when it stayed the same (the “congruency effect”). Larger effects of both switch costs and congruency were observed in humans learning the tasks by trial and error. We discuss the potential driving factors behind these very different patterns of performance for both humans and pigeons.