Climate change within the UK will affect winter starvation risk because higher temperatures reduce energy budgets and are likely to increase the quality of the foraging environment. Mass regulation in birds is a consequence of the starvation-predation risk trade-off: decreasing starvation risk because of climate change should decrease mass, but this will be countered by the effects of predation risk, because high predation risk has a negative effect on mass when foraging conditions are poor and a positive effect on mass when foraging conditions are good. We tested whether mass regulation in great tits (Parus major) across the UK was related to temporal changes in starvation risk (winter temperature 1995-2005) and spatial changes in predation risk (sparrowhawk Accipiter nisus abundance). As predicted, great tits carried less mass during later, warmer, winters, demonstrating that starvation risk overall has decreased. Also, the effects of predation risk interacted with the effects of temperature (as an index of foraging conditions), so that in colder winters higher sparrowhawk abundance led to lower mass, whereas in warmer, later, winters higher sparrowhawk abundance led to higher mass. Mass regulation in a small bird species may therefore provide an index of how environmental change is affecting the foraging environment.