Humans’ ability to learn complex sequential structure from auditory information forms a basic component of spoken language. As an exemplary case of a linguistically relevant sequential structure I investigate the learning of non-adjacent dependencies between units of sound. I will present neurophysiological studies in young infants, children and adults and integrate this with behavioral findings in order to show that complex sequential learning in the auditory domain undergoes dramatic changes across ontogenetic development including age-related decline. In contrast, the basic ability to learn non-adjacent dependencies has been found across many species, even in those that are related to humans only distantly. Computational modeling underscores that relatively simple mechanisms suffice to acquire those structures. Based on empirical evidence I will argue that the ability to learn complex structures from the auditory environment is a basic ability of primate (and maybe non-primate) brains which is specifically modified across human ontogeny in order to support the full complexity of human language.