Explosive cyclones are intense extra-tropical low pressure systems featuring large deepening rates. In the Euro-Atlantic sector, they are a major source of life-threatening weather impacts due to their associated strong wind gusts, heavy precipitation and storm surges. The wintertime variability of the North Atlantic cyclonic activity is primarily modulated by the North Atlantic Oscillation (NAO). In this study, we investigate the interannual and multi-decadal variability of explosive North Atlantic cyclones using track density data from two reanalysis datasets (NCEP and ERA-40) and a control simulation of an atmosphere/ocean coupled General Circulation Model (GCM - ECHAM5/MPIOM1). The leading interannual and multi-decadal modes of variability of explosive cyclone track density are characterized by a strengthening/weakening pattern between Newfoundland and Iceland, which is mainly modulated by the NAO at both timescales. However, the NAO control of interannual cyclone variability is not stationary in time and abruptly fluctuates during periods of 20-25 years long both in NCEP and ECHAM5/MPIOM1. These transitions are accompanied by structural changes in the leading mode of explosive cyclone variability, and by decreased/enhanced baroclinicity over the sub-polar/sub-tropical North Atlantic. The influence of the ocean is apparently important for both the occurrence and persistence of such anomalous periods. In the GCM, the Atlantic Meridional Overturning Circulation (AMOC) appears to influence the large-scale baroclinicity and explosive cyclone development over the North Atlantic. These results permit a better understanding of explosive cyclogenesis variability at different climatic timescales and might help to improve predictions of these hazardous events.