Much evidence for non-human culture comes from vocally learned displays, such as the vocal dialects and song displays of birds and cetaceans. While many oscine birds use song complexity to assess male fitness, the role of complexity in humpback whale (Megaptera novaeangliae) song is uncertain due to population-wide conformity to one song pattern. Although songs change gradually each year, the eastern Australian population also completely replaces their song every few years in cultural ‘revolutions’. Revolutions involve learning large amounts of novel material introduced from the western Australian population. We examined two measures of song structure, complexity and entropy, in the eastern Australian population over 13 consecutive years. These measures aimed to identify the role of complexity and information content in the vocal learning processes of humpback whales. Complexity was quantified at two hierarchical levels: the entire sequence of individual sound ‘units’; and the stereotyped arrangements of units which comprise a ‘theme’. Complexity increased as songs evolved over time but decreased when revolutions occurred. No correlation between complexity and entropy estimates suggests that changes to complexity may represent embellishment to the song which could allow males to stand out amidst population-wide conformity. The consistent reduction in complexity during song revolutions suggests a potential limit to the social learning capacity of novel material in humpback whales.