Submarine permafrost is more vulnerable to thawing than permafrost on land. Besides increased heat transfer from the ocean water, the penetration of salt lowers the freezing temperature and accelerates permafrost degradation. Microbial communities in thawing permafrost are expected to be stimulated by warming, but how they develop under submarine conditions is completely unknown. We used the unique records of two submarine permafrost cores from the Laptev Sea on the East Siberian Arctic Shelf, inundated about 540 and 2500 years ago, to trace how bacterial communities develop depending on duration of the marine influence and pore water chemistry. Combined with geochemical analysis, we quantified total cell numbers and bacterial gene copies and determined the community structure of bacteria using deep sequencing of the bacterial 16S rRNA gene. We show that submarine permafrost is an extreme habitat for microbial life deep below the seafloor with changing thermal and chemical conditions. Pore water chemistry revealed different pore water units reflecting the degree of marine influence and stages of permafrost thaw. Millennia after inundation by seawater, bacteria stratify into communities in permafrost, marine‐affected permafrost, and seabed sediments. In contrast to pore water chemistry, the development of bacterial community structure, diversity, and abundance in submarine permafrost appears site specific, showing that both sedimentation and permafrost thaw histories strongly affect bacteria. Finally, highest microbial abundance was observed in the ice‐bonded seawater unaffected but warmed permafrost of the longer inundated core, suggesting that permafrost bacterial communities exposed to submarine conditions start to proliferate millennia after warming.