Permafrost temperatures increased substantially at a global scale, potentially altering microbial assemblages involved in carbon mobilization before permafrost thaws. We used Arctic Shelf submarine permafrost as a natural laboratory to investigate the microbial response to long-term permafrost warming. Our work shows that millennia after permafrost warming by > 10 °C, microbial community composition and population size reflect the paleoenvironment rather than a direct effect through warming.