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. In this study, we analysed changes in fin whale (Balaenoptera physalus) songs recorded over two decades (1999–2020) across the central and eastern North Atlantic Ocean. We document a rapid replacement of song INIs (inter-note intervals) over just four singing seasons (2000/2001–2004/2005) in the southeast location of the Oceanic Northeast Atlantic (ONA) region, that co-occurred with hybrid songs (with both INIs). During the transition in song INIs (2002/2003) we show a clear geographic gradient in the occurrence of different song INIs in the whole ONA region. We also found gradual changes in song INIs (Figure 3A) and 20-Hz note (Figure 3B) and HF note (Figure 3C) peak 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.