The boreal Northeast Atlantic is strongly affected by current climate change, and large shifts in abundance and distribution of many organisms have been observed, including the dominant copepod Calanus finmarchicus, which supports the grazing food web and thus many fish populations. At the same time, large-scale declines have been observed in many piscivorous seabirds, which depend on abundant small pelagic fish. Here, we combine predictions from a niche model of C. finmarchicus with long-term data on seabird breeding success to link trophic levels. The niche model shows that environmental suitability for C. finmarchicus has declined in southern areas with large breeding seabird populations (e.g. the North Sea), and predicts that this decline is likely to spread northwards during the 21st century to affect populations in Iceland and the Faroes. In a North Sea colony, breeding success of three common piscivorous seabird species [black-legged kittiwake (Rissa tridactyla), common guillemot (Uria aalge) and Atlantic puffin (Fratercula arctica)] was strongly positively correlated with local environmental suitability for C. finmarchicus, whereas this was not the case at a more northerly colony in west Norway. Large seabird populations seem only to occur where C. finmarchicus is abundant, and northward distributional shifts of common boreal seabirds are therefore expected over the coming decades. Whether or not population size can be maintained depends on the dispersal ability and inclination of these colonial breeders, and on the carrying capacity of more northerly areas in a warmer climate.