The North Atlantic Oscillation (NAO) is the major atmospheric mode that controls winter European climate variability because its strength and phase determine regional temperature, precipitation and storm tracks. The NAO spatial structure and associated climatic impacts over Europe are not stationary making it crucial to understanding its past evolution in order to improve the predictability of future scenarios. In this regard, there has been a dramatic increase in the number of studies aimed at reconstructing past NAO variability, but the information related to decadal-scale NAO evolution beyond the last millennium is scarce and inconclusive. We present a new 2,000-year multi-annual, proxy-based reconstruction of local NAO impact, with associated uncertainties, obtained by a Bayesian approach. This new local NAO reconstruction is obtained from a mountain lacustrine sedimentary archive of the Iberian Peninsula. This geographical area is not included in previous NAO reconstructions despite being a widely used region for instrumental-based NAO measurements. We assess the main external forcings (i.e., volcanic eruptions and solar activity) on NAO variability which, on a decadal scale, show that a low number of sunspots correlate to low NAO values. By comparison with other previously published NAO reconstructions in our analyses we can test the stationarity of the solar influence on the NAO signal across a latitudinal gradient based on the position of the employed archives for each NAO reconstruction. Inconclusive results on the volcanic forcing on NAO variability over decadal time-scales indicates the need for further studies. Moreover, we highlight the potential role of other North Atlantic modes of variability (i.e., East Atlantic pattern) on the non-stationary behaviour of the NAO throughout the Common Era, likely via solar forcing.