The discovery of decadal variability of North Atlantic Oscillation (NAO) and the introduction of Arctic oscillation (AO) concept have initiated a series of paleo-AO/NAO related studies since the mid-to-late 1990s. The progress and new findings of paleo-AO/NAO works after that time were comprehensively reviewed. The new results from the observations and modelings at four key timescales were summarized in detail: ①the reconstructions of the AO/NAO annual index over the past millennium; ②the debate on AO/NAO’s trend since early Holocene; ③the weakening of AO/NAO’s amplitude during the Last Glacial Maximum; and ④the anomalous positive phase of AO/NAO during the Last Interglacial. In addition, the possible mechanism for different timescales of AO/NAO is also summarized. Furthermore, the distinction between AO/NAO’ was mean state and amplitude, which were not explicitly separated in previous studies, were comprehensively discussed. Considering the current uncertainties related to paleo-AO/NAO studies, we encourage the community to search for more proxies having longer-than-10,000-year length with annual resolution around AO/NAO highly correlated regions. Another, we encourage long-term transient modeling on AO/NAO can be performed in order to improve our understanding of the dynamics and interaction between AO/NAO’s high-frequency variability and the climatological background, so as to further improve AO/NAO’s predictability on global warming context.