The ash cloud resulting from the A. D. 2010 eruption of Eyjafjallajokull in Iceland caused severe disruption to air travel across Europe, but as a geological event it is not unprecedented. Analysis of peats and lake sediments from northern Europe has revealed the presence of microscopic layers of Icelandic volcanic ash (tephra). These sedimentary records, together with historical records of Holocene ash falls, demonstrate that Icelandic volcanoes have generated substantial ash clouds that reached northern Europe many times. Here we present the first comprehensive compilation of sedimentary and historical records of ash-fall events in northern Europe, spanning the past 7000 yr. Ash-fall events appear to have been more frequent in the past 1500 yr. It is unclear whether this reflects a true increase in eruption frequency or dispersal, or is an artifact of the records or the way in which they have been generated. In the past 1000 yr, volcanic ash clouds reached northern Europe with a mean return interval of 56 +/- 9 yr (the range of return intervals is between 6 and 115 yr). Probabilistic modeling using the ash records for the last millennium indicates that for any 10 yr period there is a 16% probability of a tephra fallout event in northern Europe. These values must be considered as conservative estimates due to the nature of tephra capture and preservation in the sedimentary record.