Warming of the Arctic led to an increase in permafrost temperatures by about 0.3 �C during the last decade. Permafrost warming is associated with increasing sediment water content, permeability, and diffusivity and could in the long term alter microbial community composition and abundance even before permafrost thaws. We studied the long-term effect (up to 2500 years) of submarine permafrost warming on microbial communities along an onshore–offshore transect on the Siberian Arctic Shelf displaying a natural temperature gradient of more than 10 �C. We analysed the in situ development of bacterial abundance and community composition through total cell counts (TCCs), quantitative PCR of bacterial gene abundance, and amplicon sequencing and correlated the microbial community data with temperature, pore water chemistry, and sediment physicochemical parameters. On timescales of centuries, permafrost warming coincided with an overall decreasing microbial abundance, whereas millennia after warming microbial abundance was similar to cold onshore permafrost. In addition, the dissolved organic carbon content of all cores was lowest in submarine permafrost after millennial-scale warming. Based on correlation analysis, TCC, unlike bacterial gene abundance, showed a significant rank-based negative correlation with increasing temperature, while bacterial gene copy numbers showed a strong negative correlation with salinity. Bacterial community composition correlated only weakly with temperature but strongly with the pore water stable isotopes �18O and �D, as well as with depth. The bacterial community showed substantial spatial variation and an overall dominance of Actinobacteria, Chloroflexi, Firmicutes, Gemmatimonadetes, and Proteobacteria, which are amongst the microbial taxa that were also found to be active in other frozen permafrost environments. We suggest that, millennia after permafrost warming by over 10 �C, microbial community composition and abundance show some indications for proliferation but mainly reflect the sedimentation history and paleoenvironment and not a direct effect through warming.