Latitudinal gradients in population dynamics can arise through regional variation in the deterministic components of the population dynamics and the stochastic factors. Here, we demonstrate an increase with latitude in the contribution of a large-scale climate pattern, the North Atlantic Oscillation (NAO), to the fluctuations in size of populations of two European hole-nesting passerine species. However, this influence of climate induced different latitudinal gradients in the population dynamics of the two species. In the great tit the proportion of the variability in the population fluctuations explained by the NAO increased with latitude, showing a larger impact of climate on the population fluctuations of this species at higher latitudes. In contrast, no latitudinal gradient was found in the relative contribution of climate to the variability of the pied flycatcher populations because the total environmental stochasticity increased with latitude. This shows that the population ecological consequences of an expected climate change will depend on how climate affects the environmental stochasticity in the population process. In both species, the effects will be larger in those parts of Europe where large changes in climate are expected.