Selection of microorganisms in marine sediment is shaped by energy-yielding electron acceptors for respiration that are depleted in vertical succession. However, some taxa have been reported to reflect past depositional conditions suggesting they have experienced weak selection after burial. In sediments underlying the Arabian Sea oxygen minimum zone (OMZ), we performed the first metagenomic profiling of sedimentary DNA at centennial-scale resolution in the context of a multi-proxy paleoclimate reconstruction. While vertical distributions of sulfate reducing bacteria and methanogens indicate energy-based selection typical of anoxic marine sediments, 5–15% of taxa per sample exhibit depth-independent stratigraphies indicative of paleoenvironmental selection over relatively short geological timescales. Despite being vertically separated, indicator taxa deposited under OMZ conditions were more similar to one another than those deposited in bioturbated intervals under intervening higher oxygen. The genomic potential for denitrification also correlated with palaeo-OMZ proxies, independent of sediment depth and available nitrate and nitrite. However, metagenomes revealed mixed acid and Entner-Dourdoroff fermentation pathways encoded by many of the same denitrifier groups. Fermentation thus may explain the subsistence of these facultatively anaerobic microbes whose stratigraphy follows changing paleoceanographic conditions. At least for certain taxa, our analysis provides evidence of their paleoenvironmental selection over the last glacial-interglacial cycle.