Legacy contamination of soils and sediments with mercury (Hg) can pose serious threats to the environment and to human health. Assessing risks and possible remediation strategies must consider the chemical forms of Hg, as different Hg species exhibit vastly different environmental behaviors and toxicities. Here, we present a study on Hg speciation and potential mobility in sediments from a chemical factory site, and soils from nearby settlement areas in the canton of Valais, Switzerland. Total Hg ranged from 0.5 to 28.4 mg/kg in the soils, and 3.5 to 174.7 mg/kg in the sediments, respectively. Elemental Hg(0) was not detectable in the soils by thermal desorption analysis. Methylmercury, the most toxic form of Hg, was present at low levels in all soils (<0.010 mg/kg; <0.8% of total Hg). Sequential extractions and thermal desorption analyses suggested that most of the Hg in the soils was present as “matrix-bound Hg(II)”, most likely associated with soil organic matter. For factory sediments, which contained less organic matter, the results suggested a higher fraction of sulfide-bound Hg. Batch extractions in different CaCl2 solutions revealed that Hg solubility was low overall, and there was no Hg-mobilizing effects of Ca2+ or Cl− in solution. Only in some of the factory sediments did high CaCl2 concentrations result in increased extractability of Hg, due to the formation of Hg-chloride complexes. Additional experiments with soil redox reactors showed that even mildly reducing conditions led to a sharp release of Hg into solution, which may be highly relevant in soils that are prone to periodic water saturation of flooding.