Several bird species have advanced the timing of their spring migration in response to recent climate change. European short-distance migrants, wintering in temperate areas, have been assumed to be more affected by change in the European climate than long-distance migrants wintering in the tropics. However, we show that long-distance migrants have advanced their spring arrival in Scandinavia more than short-distance migrants. By analyzing a long-term data set from southern Italy, we show that long-distance migrants also pass through the Mediterranean region earlier. We argue that this may reflect a climate-driven evolutionary change in the timing of spring migration.