Implicit learning involves extracting experienced regularities and statistical variation from the environment in order to improve behavior. Because knowledge of environmental structure is acquired outside of awareness, it is challenging to determine the precise nature of the information that is obtained from experience. A commonly used paradigm to study this implicit learning process is perceptual-motor sequence learning in which a covertly embedded sequence is used to create statistical structure across sequences of actions. Learning is observed by improved performance for the repeated sequence, but exactly what about the sequence is learned is unknown. It is somewhat intuitive to hypothesize that participants acquire the simplest possible statistics, which should be the least computationally demanding to track across time. In most sequence learning experiments, this means learning second-order conditional probabilities (or trigrams) in addition to basic frequency and bigram co-variation. Some prior research has suggested the possibility of multiple mechanisms based on different levels of statistics from observations of possible dissociation between deterministic, repeated sequence learning and probabilistic sequence learning tasks. An alternate idea is that a single learning mechanism capable of rapid extraction of higher-order statistics might also predict the observed learning differences due to more readily apparent long-range dependencies contained in repeated sequences compared to probabilistic sequences. In the current experiments, we manipulated the statistical information available to participants during training on an implicit sequence learning task. Participants were either trained with a traditional 12-item repeating sequence, or with probabilistic, pseudo-randomly mixed 6-item fragments of that sequence constructed to match the lower-order (trigram, bigram and frequency) statistics of the repeating sequence condition. If only the simplest necessary statistics are learned, we would expect participants to display equal sequence learning across conditions. In two experiments, we found that participants who trained on full repetitions of the sequence exhibited robustly better sequence learning than participants who had completed the probabilistic fragment training. This result implies that some higher-order statistics are acquired rapidly during practice of the repeating sequence. We built a computational simulation model to test specific hypotheses about candidate learning processes. A model restricted to low-order statistics could not fit the observed data. The best-fitting statistical learning model incorporated immediate acquisition of fourth-order conditional probabilities, two orders of magnitude more complex than strictly necessary to learn the sequence. This is particularly striking considering the exponential increase in storage capacity necessary to compute higher-order statistics among all elements of the environment. Rapid learning of high-order statistics would suggest that prior studies of probabilistic sequence learning should see lower learning rates, and observations of apparent impairment may have reflected the greater difficulty of this type of task. While the simple statistical learning mechanism we used calculates all possible high-order statistics, our results do not rule out other approaches to the computationally difficult problem (e.g., chunking mechanisms). Nevertheless, both the behavioral and modeling data suggest that participants rapidly learn higher-order statistics from sequential information, and because these are quickly and easily acquired during repeated sequence training, this type of training leads to stronger learning.