We quantified the degree to which the relationship between the geographic distribution of three major European tree species, Abies alba, Fagus sylvatica and Picea abies and January temperature (Tjan) has remained stable over the past 10,000 years. We used an extended data-set of fossil pollen records over Europe to reconstruct spatial variation in Tjan values for each 1000-year time slice between 10,000 and 3000 years BP (before present). We evaluated the relationships between the occurrences of the three species at each time slice and the spatially interpolated Tjan values, and compared these to their modern temperature ranges. Our results reveal that F. sylvatica and P. abies experienced Tjan ranges during the Holocene that differ from those of the present, while A. alba occurred over a Tjan range that is comparable to its modern one. Our data suggest the need for re-evaluation of the assumption of stable climate tolerances at a scale of several thousand years. The temperature range instability in our observed data independently validates similar results based exclusively on modeled Holocene temperatures. Our study complements previous studies that used modeled data by identifying variation in frequencies of occurrence of populations within the limits of suitable climate. However, substantial changes that were observed in the realized thermal niches over the Holocene tend to suggest that predicting future species distributions should not solely be based on modern realized niches, and needs to account for the past variation in the climate variables that drive species ranges.