Migrant birds have been trapped on the island of Helgoland (southeastern North Sea) since 1909, with methods and sampling effort remaining unchanged throughout the last four decades. In 12 short/medium-distance migrants and 12 long-distance migrants (23 passerines plus the European woodcock) sample sizes were sufficient to calculate mean spring passage (msp) times and to relate these to climate change. All but one species, passing Helgoland en route to their breeding areas (mainly in Scandinavia), show a trend towards earlier msp-time, which is significant in 7 short/medium-distance migrants and 10 long-distance migrants. The msp-times advanced by 0.05-0.28 days per year, short/medium-distance migrants not differing from long-distance migrants. In 23 out of the 24 species, earlier msp-times coincide with local warmer msp-temperatures (significantly in 11 and 7 species of the two groups, respectively). Even more striking is the relation to a large-scale phenomenon, the North Atlantic Oscillation (NAO), during the last four decades. Again, in 23 out of the 24 species, an earlier msp-time coincides with higher NAO indices (significantly in 9 and 12 species, respectively). The NAO index can also explain differences and similarities in spring migration strategies, as well as migration routes within Europe.