Among animal species, the songs of male humpback whales (Megaptera novaeangliae) are a rare example of social learning between entire populations. Understanding fine-scale similarity in song patterns and structural features will better clarify how accurately songs are learned during inter-population transmission. Here, six distinct song types (2009–2015) transmitted from the east Australian to New Caledonian populations were quantitatively analysed using fine-scale song features. Results found that New Caledonian whales learned each song type with high accuracy regardless of the pattern’s complexity. However, there were rare instances of themes (stereotyped patterns of sound units) only sung by a single population. These occurred more often in progressively changing ‘evolutionary’ songs compared to rapidly changing ‘revolutionary’ songs. Our results suggest that populations do not need to reduce complexity to accurately learn song patterns. Populations may also incorporate changes and embellishments into songs in the form of themes which are suggested to be learnt as distinct segments. Maintaining complex song patterns with such accuracy suggests significant acoustic contact, supporting the hypothesis that song learning may occur on shared feeding grounds or migration routes. This study improves the understanding of inter-population mechanisms for large-scale cultural transmission in animals.