Under current global warming, high-elevation regions are expected to experience faster warming than low-elevation regions. However, due to the lack of studies based on long-term large-scale data, the relationship between tree spring phenology and the elevation-dependent warming is unclear. Using 652k records of leaf unfolding of five temperate tree species monitored during 1951-2013 insitu in Europe, we discovered a nonlinear trend in the altitudinal sensitivity (S-A, shifted days per 100m in altitude) in spring phenology. A delayed leaf unfolding (2.7 +/- 0.6days per decade) was observed at high elevations possibly due to decreased spring forcing between 1951 and 1980. The delayed leaf unfolding at high-elevation regions was companied by a simultaneous advancing of leaf unfolding at low elevations. These divergent trends contributed to a significant increase in the S-A (0.36 +/- 0.07days 100/m per decade) during 1951-1980. Since 1980, the S-A started to decline with a rate of -0.32 +/- 0.07days 100/m per decade, possibly due to reduced chilling at low elevations and improved efficiency of spring forcing in advancing the leaf unfolding at high elevations, the latter being caused by increased chilling. Our results suggest that due to both different temperature changes at the different altitudes, and the different tree responses to these changes, the tree phenology has shifted at different rates leading to a more uniform phenology at different altitudes during recent decades.