Most studies of acoustic communication focus on short units of vocalization such as songs, yet these units are often hierarchically organized into higher-order sequences and, outside human language, little is known about the drivers of sequence structure. Here, we investigate the organization, transmission and function of vocal sequences sung by male Albert's lyrebirds (Menura alberti), a species renowned for vocal imitations of other species. We quantified the organization of mimetic units into sequences, and examined the extent to which these sequences are repeated within and between individuals and shared among populations. We found that individual males organized their mimetic units into stereotyped sequences. Sequence structures were shared within and to a lesser extent among populations, implying that sequences were socially transmitted. Across the entire species range, mimetic units were sung with immediate variety and a high acoustic contrast between consecutive units, suggesting that sequence structure is a means to enhance receiver perceptions of repertoire complexity. Our results provide evidence that higher-order sequences of vocalizations can be socially transmitted, and that the order of vocal units can be functionally significant. We conclude that, to fully understand vocal behaviours, we must study both the individual vocal units and their higher-order temporal organization.