Using a very high resolution 3D numerical model we investigate the tidal dynamics in the Strait of Messina. We show that different stratifications at the southern boundaries, consistent with observed stratifications in the Ionian approaches to the Strait, yield different mean sea level heights. On this basis we search for long-term variations in sea level heights measured in the tidal stations of Catania, Messina and Marseille, and associate them with the concomitant phase of dominant modes of interannual-to-decadal climate variability in the Euro-Mediterranean sector. We focus on the atmospheric North Atlantic Oscillation (NAO) and on the Adriatic-Ionian Bimodal Oscillating System (BiOS) to illustrate the grand variability in sea level teleconnections during the last four decades. In particular, observations reveal a strong imprint of both NAO and BiOS on all sea level records in the 21st century, when NAO and BiOS are inversely correlated. In the 1990s, a well known period of persistent positive NAO anomalies, the NAO imprint on sea level becomes weaker compared to the most recent period, although it remains clear on decadal trends, while the BiOS shows very weak positive variability. In the 1970s and early 1980s, when the NAO was on a neutral phase with weak variability, the NAO imprint on sea levels is weakest, and sea levels in Marseille and Sicily anticorrelate with each other, in contrast to the positive correlations found during the later periods. Based on these observational evidence, we discuss how our modeling results provide a basis to understand the local dynamics that contributed to determine such observed decadal variability.