Interactions and feedbacks between abundant surface waters and permafrost fundamentally shape lowland Arctic landscapes. Sublake permafrost is maintained when the maximum ice thickness (MIT) exceeds lake depth and mean annual bed temperatures (MABTs) remain below freezing. However, declining MIT since the 1970s is likely causing talik development below shallow lakes. Here we show high-temperature sensitivity to winter ice growth at the water-sediment interface of shallow lakes based on year-round lake sensor data. Empirical model experiments suggest that shallow (1 m depth) lakes have warmed substantially over the last 30 years (2.4°C), with MABT above freezing 5 of the last 7 years. This is in comparison to slower rates of warming in deeper (3 m) lakes (0.9°C), with already well-developed taliks. Our findings indicate that permafrost below shallow lakes has already begun crossing a critical thawing threshold approximately 70 years prior to predicted terrestrial permafrost thaw in northern Alaska.