From comprehending language to learning new dance moves, extracting complex relationships between sequences of input is a key feature of human cognition. Prior studies have predominantly explored the cognitive mechanisms of structure learning using Markov sequences, where each element depends only on the previous one. Real-world experience, however, is rife with complex dependencies beyond Markov processes. Here, we study the effects of non-Markov dependencies on sequence learning by leveraging graph learning approaches. We introduce a motor sequence task in which transitional probabilities between pairs of stimuli are identical from a Markov perspective, but differ on higher-order non-Markov dependencies. We find that participants are better able to anticipate stimuli with higher non-Markov probabilities, providing corroboratory evidence that humans are sensitive to statistical structure beyond Markov dependencies. Further, behavior differed from other participants trained only on Markov sequences. Overall, this work demonstrates that humans can rapidly learn and represent statistical dependencies beyond the Markov regime.