While subsurface microbial communities are generally structured through in situenvironmental conditions such as the availability of electron acceptors and donors, recent studies implied that a subset of these microbial taxa were present at the time of deposition and formed a genetic archive of bacterial species (i.e., a bacterial paleome) that can provide information about the paleodepositional environment. However, additional high sampling resolution records spanning key climate stages are required to verify this claim. Recent studies have shown that sediments underlying the permanently stratified and anoxic Black Sea contain well preserved photic zone-derived plankton DNA suitable for the reconstruction of past ecosystem-climate interactions. It is therefore to be expected that a subseafloor bacterial paleome is present in the Black Sea that will reveal a correlation with known paleoenvironmental changes in the region. To test this hypothesis, we used a shotgun metagenomic approach to study the taxonomic and functional diversity of the Black Sea’s subsurface microbiome and compared community changes with the timing of Holocene climate shifts. Obligate aerobic bacteria made the largest contribution to the observed shifts in microbial communities associated with known Holocene climate stages and transitions and were likely seeded from the water column and did not undergo postdepositional selection. Presumably active anaerobic bacterial communities showed the most significant response to the timing of the establishment of modern-day environmental conditions 5200 years ago, previously shown to have resulted in a shift in planktonic communities and the type of organic matter being sequestered. No significant shift in the subseafloor microbiome was observed as a result of gradual environmental changes that occurred after the marine reconnection, 9 ka ago.