Constant interaction with a dynamic environment — from riding a bicycle to segmenting speech — makes sensitivity to the sequential structure of the world a crucial dimension of the cognitive system. Accounts of sequence learning vary widely, with some authors arguing that parsing and segmentation processes are central, and others defending the notion that sequence learning involves mere memorization. In this paper, we argue that sequence knowledge is essentially statistical in nature and that sequence learning involves simple associative prediction mechanisms. We focus on a choice reaction situation introduced by Lee (1997), in which participants were exposed to material that follows an extremely simple rule, namely that stimuli are selected randomly but never appear more than once in a legal sequence. Perhaps surprisingly, people can learn this rule very well. Or do they? We offer a conceptual replication of the original finding, but a very different interpretation of the results, as well as simulation work that makes it clear how highly abstract dimensions of the stimulus material can in fact be learned based on elementary associative mechanisms.