Reactions of dissolved organic matter (DOM) with aqueous sulfide (termed sulfurization) in anoxic environments can substantially increase DOM’s reduced sulfur functional group content. Sulfurization may affect DOM–trace metal interactions, including complexation and metal-containing particle precipitation, aggregation, and dissolution. Using a diverse suite of DOM samples, we found that susceptibility to additional sulfur incorporation via reaction with aqueous sulfide increased with increasing DOM aromatic-, carbonyl-, and carboxyl-C content. The role of DOM sulfurization in enhancing Hg bioavailability for microbial methylation was evaluated under conditions typical of Hg methylation environments (μM sulfide concentrations and low Hg-to-DOM molar ratios). Under the conditions of predicted metacinnabar supersaturation, microbial Hg methylation increased with increasing DOM sulfurization, likely reflecting either effective inhibition of metacinnabar growth and aggregation or the formation of Hg(II)–DOM thiol complexes with high bioavailability. Remarkably, Hg methylation efficiencies with the most sulfurized DOM samples were similar (>85% of total Hg methylated) to that observed in the presence of l-cysteine, a ligand facilitating rapid Hg(II) biouptake and methylation. This suggests that complexes of Hg(II) with DOM thiols have similar bioavailability to Hg(II) complexes with low-molecular-weight thiols. Overall, our results are a demonstration of the importance of DOM sulfurization to trace metal and metalloid (especially mercury) fate in the environment. DOM sulfurization likely represents another link between anthropogenic sulfate enrichment and MeHg production in the environment.