Long-term predictions of regional changes are of utmost importance due to their high societal and economic impacts. Yet, current projections are of limited skill as they rely on satellite records that are relatively short compared to the timescales of interest, and also due to the presence of a significant anthropogenic trend superposed with low-frequency natural variability. Recent simulations of past climates provide a unique opportunity to separate external perturbations from internal climate anomalies and to attribute the latter to the statistical distributions of climate and weather patterns on shorter timescales. Here we study such changes by applying a recently introduced data analysis technique called Nonlinear Laplacian Spectral Analysis (NLSA) to a range of models and observations. We focus on the Indo-Pacific Ocean variability and recover modes across a range of timescales, including the variance-dominating ENSO, its seasonal and multidecadal modulations, and others. As such, our study unambiguously clarifies interdependencies between interannual modes which are sometimes treated in the climate science community as independent, but also lead to the identification of previously-unknown decadal to centennial modes. Furthermore we demonstrate that a newly-detected pattern, called West Pacific Multidecadal Mode, projects significantly onto other parts of the coupled climate system, and in particular Australian hydroclimate over many timescales. We also discuss the possible linkages and physical mechanisms connecting Indo-Pacific Ocean variability with the regional statistics of other high- and low-frequency extremes. Moreover, we compare our results with an NLSA-based analysis of various past and future climate scenarios, and reveal how internally-driven fluctuations compare with the ones attributed to impacts driven by NLSA-derived trends. Extensions of this work aiming to improve model fidelity are also discussed.