Secondary sexual traits have high heritabilities and are exposed to strong, environmentally sensitive selection, and so are expected to evolve rapidly in response to sustained environmental change. We examine the eco-evolutionary dynamics of ornament expression in a long-term study population of collared flycatchers, Ficedula albicollis, in which forehead patch size, which positively influences male reproductive success, declined markedly over 34 years. Annual fitness selection on forehead patch size switched from positive to negative during the study, a reversal that is accounted for by rising spring temperatures at the breeding site: highly ornamented males were selectively favoured following cold breeding seasons but selected against following warm breeding seasons. An ‘individual animal model’ describes a decline in the genetic values of breeding males during the study, which simulations showed was unlikely to result from drift alone. These results are thus consistent with adaptive evolution of a sexually selected trait in response to climate change.