In four experiments we investigated whether incidental task sequence learning occurs when no instructional task cues are available (i.e. with univalent stimuli). We manipulated task sequence by presenting three simple binary-choice tasks (colour, form or letter case decisions) in regular repeated or random order. Participants were required to use the same two response keys for each of the tasks. We manipulated response sequence by ordering the stimuli so as to produce either a regular or a random order of left versus right-hand key presses. When sequencing in both, or either, separate stream (i.e. task sequence and/or response sequence) was changed to random, only those participants who had processed both sequences together showed evidence of sequence learning in terms of significant response time disruption (Experiments 1–3). This effect disappeared when the sequences were uncorrelated (Experiment 4). The results indicate that only the correlated integration of task sequence and response sequence produced a reliable incidental learning effect. As this effect depends on the predictable ordering of stimulus categories, it suggests that task sequence learning is perceptual rather than conceptual in nature.