Marine sediments impacted by urban and industrial pollutants are typically exposed to reducing conditions and represent major reservoirs of toxic mercury species. Mercury methylation mediated by anaerobic microorganisms is favored under such conditions, yet little is known about potential microbial mechanisms for mercury detoxification. We used culture-independent (metagenomics, metabarcoding) and culture-dependent approaches in anoxic marine sediments to identify microbial indicators of mercury pollution and analyze the distribution of genes involved in mercury reduction (merA) and demethylation (merB). While none of the isolates featured merB genes, 52 isolates, predominantly affiliated with Gammaproteobacteria, were merA positive. In contrast, merA genes detected in metagenomes were assigned to different phyla, including Desulfobacterota, Actinomycetota, Gemmatimonadota, Nitrospirota, and Pseudomonadota. This indicates a widespread capacity for mercury reduction in anoxic sediment microbiomes. Notably, merA genes were predominately identified in Desulfobacterota, a phylum previously associated only with mercury methylation. Marker genes involved in the latter process (hgcAB) were also mainly assigned to Desulfobacterota, implying a potential central and multifaceted role of this phylum in the mercury cycle. Network analysis revealed that Desulfobacterota were associated with anaerobic fermenters, methanogens and sulfur-oxidizers, indicating potential interactions between key players of the carbon, sulfur and mercury cycling in anoxic marine sediments.