A comprehensive analysis of data collected over the last five decades on the Romanian Black Sea coast (meteo & hydrological data, sea level, topographic maps, satellite imagery, GPS surveys and beach profiles) demonstrate that the North-Atlantic Oscillation (NAO) exerts a multi-decadal influence on the Romanian Black Sea coastal environment components. Accordingly, temperature positive anomalies are directly correlated to NAO positive phases, while precipitation, Danube discharge (including floods occurrence) and wind regime variability is inversely controlled by NAO fluctuations (out-of-phase report). Moreover, the present study reveals that coastal morphodynamics appears to be influenced by NAO via coastal storm regime. The analysis of Danube delta coast evolution revealed two time intervals with different coastal dynamics patterns: i) high shoreline mobility during 1961-1979 interval with high retreating and advancing rates, and ii) low shoreline mobility afterwards (1979-2006). The most aggressive erosion affects the sedimentary divergence zones which experienced the highest rates of coastal retreat for all 45-years study period (~20 m/yr / ~10 m/yr during 1961-1979 / 1979-2006 time interval), whereas the shoreline advanced fastest along the coast of active lobes (i.e., Chilia and Sf. Gheorghe lobes). During the second interval (1979-2006), the decrease of shoreline changes rates, reported to first period (1961-1979), was similar for the erosive beaches (with 55-66%) but non-uniform for the accretionary coasts (20-61% for open beaches and 80% for the sheltered secondary deltas). Wind data analysis reveals a good connection between multi-decadal winter storm frequency along the Danube delta coast and negative NAO phases (r = -0.76). The results of the present study clearly show that shoreline changes at decadal time scales are also ultimately driven by the NAO which controls the storminess on the Danube delta coast.