Animal songs can change within and between populations as the result of different evolutionary processes. When these processes include cultural transmission, the social learning of information or behaviours from conspecifics, songs can undergo rapid evolutions because cultural novelties can emerge more frequently than genetic mutations. Understanding these song variations over large temporal and spatial scales can provide insights into the patterns, drivers and limits of song evolution that can ultimately inform on the species’ capacity to adapt to rapidly changing acoustic environments. Here, we analysed changes in fin whale (Balaenoptera physalus) songs recorded over two decades across the central and eastern North Atlantic Ocean. We document a rapid replacement of song INIs (inter-note intervals) over just four singing seasons, that co-occurred with hybrid songs (with both INIs), and a clear geographic gradient in the occurrence of different song INIs during the transition period. We also found gradual changes in INIs and note frequencies over more than a decade with fin whales adopting song changes. These results provide evidence of vocal learning in fin whales and reveal patterns of song evolution that raise questions on the limits of song variation in this species.