From 1976 to 1997 passerines were mist-netted and ringed on the island of Christiansø, in the Baltic Sea. Here we present analyses of phenological changes (i.e. time of arrival) for 25 species based on the entire populations of mist-netted songbirds during spring migration. We used two approaches (least square and quantile regression) to test for changes in arrival time of first individuals and three different parts of the songbird populations (i.e. first 5%, 50% and 95% of the total number of trapped individuals corrected for trapping effort). Our results generally confirm earlier spring arrival of migratory passerines with an overall earlier arrival of 0.26 days per year. Changes in the arrival time of first individuals are often the only data available. They are typically analysed on the assumption that they are representative of their respective population. We found a unidirectional, significant change towards earlier arrival for all four measures of arrival timing which seem to support this. However, the four measures of arrival are changing at different rates. First individuals changed arrival time more rapidly than the first 5%, 50% and 95% of the spring total. Such differences are likely to be important for our understanding of population-dynamic changes in relation to climate change. These differences may also have long-term evolutionary consequences. Migration distance seems to affect the degree of change in arrival time, but we found no difference between species wintering in different regions of Africa.