Vocal communication systems have a set of rules that govern the arrangement of acoustic signals, broadly defined as ‘syntax’. However, there is a limited understanding of potentially shared or analogous rules across vocal displays in different taxa. Recent work on songbirds has investigated syntax using network-based modelling. This technique quantifies features such as connectivity (adjacent signals in a sequence) and recurring patterns. Here, we apply network-based modelling to the complex, hierarchically structured songs of humpback whales (Megaptera novaeangliae) from east Australia. Given the song’s annual evolving pattern and the cultural conformity of males within a population, network modelling captured the patterns of multiple song types over 13 consecutive years. Song arrangements in each year displayed clear “small-world” network structure, characterised by clusters of highly connected sounds. Transitions between these connected sounds further suggested a combination of both structural stability and variability. Small-world network structure within humpback songs may facilitate the characteristic and persistent vocal learning observed. Similar small-world structures and transition patterns are found in several birdsong displays, indicating common syntactic patterns among vocal learning in multiple taxa. Understanding the syntactic rules governing vocal displays in multiple, independently evolving lineages may indicate what rules or structural features are important to the evolution of complex communication, including human language.