The risk of extreme heat waves in Europe like the unprecedented one of summer 2003 is likely to increase in the future, calling for increased understanding of these phenomena. From an analysis of meteorological records over 58 years, we show that hot summers are preceded by winter rainfall deficits over Southern Europe. Subsequent drought and heat spreads northward throughout Europe in early summer, due to atmospheric transport of anomalously warm and dry air from Southern Europe in southerly wind episodes. This is shown by the observations and supported by mesoscale meteorological sensitivity simulations for Summer 1994. Moreover previous winter and early spring rainfall frequency in the Mediterranean regions is correlated with summer temperature in central continental Europe. These results emphasize the critical role of the water reservoir in the soil of continental Mediterranean areas for the maintenance of European climate.