East Asia experienced a record-breaking cold event during the 2015/16 boreal winter, with pronounced impacts on livelihood in the region. We find that this large-scale cold spell can be attributed to the concurrent super El Niño event in the tropical Pacific. Our analysis reveals that all super El Niño winters (1982/83, 1997/98, and 2015/16) were accompanied by a rapid sub-seasonal North Atlantic Oscillation (NAO)/Arctic Oscillation (AO) phase reversal from a positive to a negative state during early January, which was largely caused by the interaction of these super El Niño events with the subtropical jet annual cycle. The NAO/AO phase transition leads to a rapidly strengthened Siberian High, which favors southward intrusions of cold air to East Asia and thus causes severe local cooling. Similar cold spells can also be detected over Northern Europe associated with the fast sub-seasonal NAO/AO phase reversal. Due to the weaker amplitude of the ENSO forcing, these sub-seasonal atmospheric responses cannot be detected for moderate El Niño events. The super El Niño associated sub-seasonal signal of the East Asian and Northern Europe wintertime temperature responses carries important implications for future predictability of regional extreme events.