Modes of climate variability affect global and regional climates on different spatio-temporal scales, and they have important impacts on human activities and ecosystems. As these modes are a useful tool for simplifying the understanding of the climate system, it is crucial that we gain improved knowledge of their long-term past evolution and interactions over time to contextualise their present and future behaviour. We review the literature focused on proxy-based reconstructions of modes of climate variability during the Holocene (i.e., the last 11.7 thousand years) with a special emphasis on i) proxy-based reconstruction methods; ii) available proxy-based reconstructions of the main modes of variability, i.e., El Niño Southern Oscillation, Pacific Decadal Variability, Atlantic Multidecadal Variability, the North Atlantic Oscillation, the Southern Annular Mode and the Indian Ocean Dipole; iii) major interactions between these modes; and iv) external forcing mechanisms related to the evolution of these modes. This review shows that modes of variability can be reconstructed using proxy-based records from a wide range of natural archives, but these reconstructions are scarce beyond the last millennium, partly due to the lack of robust chronologies with reduced dating uncertainties, technical issues related to proxy calibration, and difficulty elucidating their stationary impact (or not) on regional climates over time. While for each mode the available reconstructions tend to agree at mutidecadal timescales, they show notable disagreement on shorter timescales beyond the instrumental period. The reviewed evidence suggests that the intrinsic variability of modes can be modulated by external forcing, such as orbital, solar, volcanic, and anthropogenic forcing. The review also highlights some modes experience higher variability over the instrumental period, which is partly ascribed to anthropogenic forcing. These features stress the paramount importance of further studying their past variations using long climate-proxy records for the progress of climate science.