The present day interest in understanding whether and how methane, preserved in seabed reservoirs, can escape to the atmosphere suggests a need to review sub-sea permafrost observations and to re-examine available sub-sea permafrost models. Currently, the models of sub-sea permafrost evolution significantly vary in employed physical assumptions regarding the paleo-geographic scenario, geological structure, thermal properties, initial temperature distribution, and geothermal heat flux. This work aims to review the underlying assumptions of these models as well as to incorporate recent findings, and hence develop an up-to-date model of the sub-sea permafrost dynamics at the Laptev Sea shelf. In particular, the developed sub-sea permafrost model incorporates the thermokarst and land-ocean interaction theory, and shows that the sediment salinity and a temperature-based parametrization of the unfrozen water content are critical factors influencing sub-sea permafrost dynamics. From the numerical calculations, we suggest development of open taliks underneath submerged thaw lakes within a large area of the shelf. This work is supported by the Government of the Russian Federation (mega-grant #2013-220-04-157)