New sclerochronological data suggest that a variability comparable to the North Atlantic Oscillation (NAO) was already present during the middle Oligocene, about 20 Myr earlier than formerly assumed. Annual increment width data of long-lived marine bivalves of Oligocene (30–25 Ma) strata from Central Europe revealed a distinct quasi-decadal climate variability modulated on 2–12 (mainly 3–7) year cycles. As in many other modern bivalves, these periodic changes in shell growth were most likely related to changes in primary productivity, which in turn, were coupled to atmospheric circulation patterns. Stable carbon isotope values of the shells (δ13Cshell) further corroborated the link between shell growth and food availability. Sub-decal oscillations in the 3–7 year band in other annually resolved fossil archives were often interpreted as El Niño-Southern Oscillation (ENSO) cycles. This possibility is discussed in the present study. However, combined shell-derived proxy and numerical climate model data lend support to the interpretation of a NAO-like variability. According to numerical climate models, winter sea-level pressure (wSLP) and precipitation rate (wPR) across Central Europe during the Oligocene exhibited a pattern similar to the modern NAO. The simulated NAO index for the Oligocene shows periodicities coherent with those revealed by the proxy data (2.5–6 years), yet, on shorter wavelengths than the modern NAO (biennial and 6–10 year cycles). Likely, the different paleogeography and elevated atmospheric CO2 concentrations not only influenced the sea-level pressure pattern, but also the temporal variability of the NAO precursor. The present study represents the first attempt to characterize the inter-annual climate variability in Central Europe during the Oligocene and sets the basis for future studies on the early phase of the Cenozoic icehouse climate state.