Seabird population size is intimately linked to the physical, chemical, and biological processes of the oceans. Yet, the overall effects of long-term changes in ocean dynamics on seabird colonies are difficult to quantify. Here, we used dated lake sediments to reconstruct ~10,000-years of seabird dynamics in the Northwest Atlantic to determine the influences of Holocene-scale climatic oscillations on colony size. On Baccalieu Island (Newfoundland and Labrador, Canada) – where the world’s largest colony of Leach’s storm-petrel (Hydrobates leucorhous Vieillot 1818) currently breeds – our data track seabird colony growth in response to warming during the Holocene Thermal Maximum (ca. 9,000 to 6,000 BP). From ca. 5,200 BP to the onset of the Little Ice Age (ca. 550 BP), changes in colony size were correlated to variations in the North Atlantic Oscillation (NAO). By contrasting the seabird trends from Baccalieu Island to millennial-scale changes of storm-petrel populations from Grand Colombier Island (an island in the Northwest Atlantic that is subjected to different ocean climate), we infer that changes in NAO influenced the ocean circulation, which translated into, among many things, changes in pycnocline depth across the Northwest Atlantic basin where the storm-petrels feed. We hypothesize that the depth of the pycnocline is likely a strong bottom-up control on surface-feeding storm-petrels through its influence on prey accessibility. Since the Little Ice Age, the effects of ocean dynamics on seabird colony size have been altered by anthropogenic impacts. Subsequently, the colony on Baccalieu Island grew at an unprecedented rate to become the world’s largest resulting from favourable conditions linked to climate warming, increased vegetation (thereby nesting habitat), and attraction of recruits from other colonies that are now in decline. We show that although ocean dynamics were an important driver of seabird colony dynamics, its recent influence has been modified by human interference.