Severe storms defined as 3-hourly pressure changes exceeding an extreme magnitude, were carefully manually quality-controlled and analyzed at stations in the UK and Iceland which had at least 45 years of digitized data. Iceland showed significant distribution differences between the periods before and after 1980 with a tendency towards less extreme severe events in latter decades. In contrast, the UK regions have tended towards larger magnitude events in recent decades, particularly in the more southerly regions. There has been a significant increase in the number of severe storms over the UK as a whole since the 1950s, however, this may not be unusual in longer-term variability. For both the UK and Iceland in winter these changes in severe storms appear to be related to changes in the North Atlantic Oscillation (NAO) but UK changes during October to December do not appear to be related to changes in the NAO.