The North Water (NOW) polynya is one of the most productive marine areas of the Arctic and an important breeding area for millions of seabirds. There is, however, little information on the dynamics of the polynya or the bird populations over the long term. Here, we used sediment archives from a lake and peat deposits along the Greenland coast of the NOW polynya to track long-term patterns in the dynamics of the seabird populations. Radiocarbon dates show that the thick-billed murre (Uria lomvia) and the common eider (Somateria mollissima) have been present for at least 5500 cal. years. The first recorded arrival of the little auk (Alle alle) was around 4400 cal. years bp at Annikitsoq, with arrival at Qeqertaq (Salve Ø) colony dated to 3600 cal. years bp. Concentrations of cadmium and phosphorus (both abundant in little auk guano) in the lake and peat cores suggest that there was a period of large variation in bird numbers between 2500 and 1500 cal. years bp. The little auk arrival times show a strong accord with past periods of colder climate and with some aspects of human settlement in the area.