The ability to process structured sequences of sounds lies at the basis of human language processing. Language is characterized by a high level of structural complexity including non-adjacent dependencies where the relationships between elements can span multiple intervening elements. Understanding how such structures can be learned is of particular interest for understanding how language develops and how it evolved. In recent years advances have been made in identifying the constraints and conditions under which non-adjacent dependencies can be learned across development and different species. Yet, in humans, online and offline methods suggest markedly different developmental timelines. Notably, human infants seem to outperform adults in online learning during mere exposure. Comparative studies with non-human primates reveal the auditory sequence learning capacities and limitations of our close phylogenetic relatives. Initial findings suggest that primates show similar learning abilities to human infants revealing an evolutionary preserved computational ability to automatically extract non-adjacent relations from auditory sequences. The pattern found across ontogeny and phylogeny is consistent with the idea that language evolution was in part enabled by powerful auditory sequencing abilities. These abilities were potentially boosted in humans by improvements in higher-order cognitive abilities that allowed us to link sequential patterns to abstract semantic and syntactic representations.