Protandry is a widespread life-history phenomenon describing how males precede females at the site or state of reproduction. In migratory birds, protandry has an important influence on individual fitness, the migratory syndrome, and phenological response to climate change. Despite its significance, accurate analyses on the dynamics of protandry using data sets collected at the breeding site, are lacking. Basing our study on records collected during two time periods, 1979 to 1988 and 2006 to 2016, we aim to investigate protandry dynamics over 38 years in a breeding population of willow warblers (Phylloscopus trochilus). Change in the timing of arrival was analyzed in males and females, and protandry (number of days between male and female arrival) was investigated both at population level and within breeding pairs. Our results show advancement in the arrival time at the breeding site in both sexes, but male arrival has advanced to a greater extent, leading to an increase in protandry both at the population level and within breeding pairs. We did not observe any change in sex ratio that could explain the protandry increase, but pronounced temperature change has occurred and been reported in the breeding area and along the migratory route. Typically, natural selection opposes too early arrival in males, but given warmer springs, this counteracting force may be relaxing, enabling an increase in protandry. We discuss whether our results suggest that climate change has induced sex-specific effects, if these could be evolutionary and whether the timing of important life-history stages such as arrival at the breeding site may change at different rates in males and females following environmental shifts.