Sulfate-reducing microorganisms (SRMs) often compete with methanogens for common substrates. Due to thermodynamic reasons, SRMs should outcompete methanogens in the presence of sulfate. However, many studies have documented coexistence of these microbial groups in natural environments, suggesting that thermodynamics alone cannot explain the interactions among them. In this study, we investigated how SRMs compete with the established methanogenic communities in sediment from a long-term, electron acceptor-depleted, asphalt-exposed ecosystem and how they affect the composition of the organic material. We hypothesized that, upon addition of sulfate, SRMs (i) outcompete the methanogenic communities and (ii) markedly contribute to transformations of the organic material. We sampled sediments from the test and proximate control sites under anoxic conditions and incubated them in seawater medium with or without sulfate. Abundance and activity pattern of SRMs and methanogens, as well as the total prokaryotic community, were followed for 6 weeks by using qPCR targeting selected marker genes. Some of these genes were also subjected to amplicon sequencing to assess potential shifts in diversity patterns. Alterations of the organic material in the microcosms were determined by mass spectrometry. Our results indicate that the competition of SRMs with methanogens upon sulfate addition strongly depends on the environment studied and the starting microbiome composition. In the asphalt-free sediments (control), the availability of easily degradable organic material (mainly plant-derived) allows SRMs to use a larger variety of substrates, reducing interspecies competition with methanogens. In contrast, the abundant presence of recalcitrant compounds in the asphalt-exposed sediment was associated with a strong competition between SRMs and methanogens, ultimately detrimental for the latter. Our data underpin the importance of the quality of bioavailable organic materials in anoxic environments as a driver for microbial community structure and function.