Climate change is expected to have profound ecological effects, yet shifts in competitive abilities among species are rarely studied in this context. Blue tits (Cyanistes caeruleus) and great tits (Parus major) compete for food and roosting sites, yet coexist across much of their range. Climate change might thus change the competitive relationships and coexistence between these two species. Analysing four of the highest-quality, long-term datasets available on these species across Europe, we extend the textbook example of coexistence between competing species to include the dynamic effects of long-term climate variation. Using threshold time-series statistical modelling, we demonstrate that long-term climate variation affects species demography through different influences on density-dependent and density-independent processes. The competitive interaction between blue tits and great tits has shifted in one of the studied sites, creating conditions that alter the relative equilibrium densities between the two species, potentially disrupting long-term coexistence. Our analyses show that long-term climate change can, but does not always, generate local differences in the equilibrium conditions of spatially structured species assemblages. We demonstrate how long-term data can be used to better understand whether (and how), for instance, climate change might change the relationships between coexisting species. However, the studied populations are rather robust against competitive exclusion.