The internal climate variability (ICV) sets limits on predictability of future sea level changes. The uncertainties induced by the ICV are commonly estimated from a spread across sea level predictions obtained in Global Climate Models under the same forcing but with slightly different initial conditions. Whether the uncertainties induced by the ICV are strong enough to mask the contribution of external drivers (i.e. solar radiation, state of the atmosphere, etc) is a topical issue of many current studies. Here, we analyze sea level variations across the Large Ensembles (LE) of Community Climate System Model (CCSM) and Community Earth System Model (CESM) obtained under different warming scenarios over 1920-2017 and compare them with observations provided by several century-long tidal records. We demonstrate a "long memory" persistent behavior of the modeled sea level variations on decadal-to-centennial time scales in the extratropical and polar regions and notice its general agreement with fluctuations in the observed sea level. This persistent long-range correlated behavior arises from the complex internal dynamics of the climate and can lead to spontaneous fluctuations of sea level. The predictability of sea level changes is , by consequence, tightly linked to the interplay between the persistent fluctuations and the modes of climate variability. We estimate the uncertainties of modeled sea level changes by using a theory of power law correlations and by the spread among the CESM members and compare them with the analysis of observed sea levels.