Climate change in the Arctic is occurring rapidly, and projections suggest the complete loss of summer sea ice by the middle of this century1. The sensitivity of permanently frozen ground (permafrost) in the Northern Hemisphere to warming is less clear, and its long-term trends are harder to monitor than those of sea ice. Here we use palaeoclimate data to show that Siberian permafrost is robust to warming when Arctic sea ice is present, but vulnerable when it is absent. Uranium-lead chronology of carbonate deposits (speleothems) in a Siberian cave located at the southern edge of continuous permafrost reveals periods in which the overlying ground was not permanently frozen. The speleothem record starts 1.5 million years ago (Ma), a time when greater equator-to-pole heat transport led to a warmer Northern Hemisphere2. The growth of the speleothems indicates that permafrost at the cave site was absent at that time, becoming more frequent from about 1.35 Ma, as the Northern Hemisphere cooled, and permanent after about 0.4 Ma. This history mirrors that of year-round sea ice in the Arctic Ocean, which was largely absent before about 0.4 Ma (ref. 3), but continuously present since that date. The robustness of permafrost when sea ice is present, as well as the increased permafrost vulnerability when sea ice is absent, can be explained by changes in both heat and moisture transport. Reduced sea ice may contribute to warming of Arctic air4-6, which can lead to warming far inland7. Open Arctic waters also increase the source of moisture and increase autumn snowfall over Siberia, insulating the ground from low winter temperatures8-10. These processes explain the relationship between an ice-free Arctic and permafrost thawing before 0.4 Ma. If these processes continue during modern climate change, future loss of summer Arctic sea ice will accelerate the thawing of Siberian permafrost.