Constant interaction with a dynamic environment-from riding a bicycle to segmenting speech-makes sensitivity to the sequential structure of the world a fundamental dimension of information processing. Accounts of sequence learning vary widely, with some authors arguing that parsing and segmentation processes are central, and others proposing 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 a single abstract 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 can 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. We conclude that, when relevant, memory is optimized to facilitate responding to events that have not occurred recently, and that sequence learning in general always involves sensitivity to repetition distance.