The amount of genetic variance underlying a phenotypic trait and the strength of selection acting on that trait are two key parameters that determine any evolutionary response to selection. Despite substantial evidence that, in natural populations, both parameters may vary across environmental conditions, very little is known about the extent to which they may covary in response to environmental heterogeneity. Here we show that, in a wild population of great tits (Parus major), the strength of the directional selection gradients on timing of breeding increased with increasing spring temperatures, and that genotype-by-environment interactions also predicted an increase in additive genetic variance, and heritability, of timing of breeding with increasing spring temperature. Consequently, we therefore tested for an association between the annual selection gradients and levels of additive genetic variance expressed each year; this association was positive, but non-significant. However, there was a significant positive association between the annual selection differentials and the corresponding heritability. Such associations could potentially speed up the rate of micro-evolution and offer a largely ignored mechanism by which natural populations may adapt to environmental changes.