A detailed analysis of the tidal regime in Venice, Italy, during the last century shows that the frequency and magnitude of high tides are correlated to interdecadal climatic oscillations. The monthly high tide maxima and the average elevation of all high tides are negatively correlated to the North Atlantic Oscillation (NAO), to the Arctic Oscillation (AO), to the East Atlantic -- West Russian oscillation (EA-WR), and to the Polar Eurasia teleconnection (POL). The correlation is high during winter months for all four indices, whereas in the fall, when most of the city floods occur, the AO and the EA-WR exert a stronger influence on the tidal regime. During negative phases of the climate indices both the average elevation of high tides and the frequency of flooding increase consistently, with negative effects on the city and its monuments.