The atmospheric lifetime of mercury is greatly impacted by redox chemistry resulting from the high deposition rate of reactive mercury (Hg(II)) compared to elemental mercury (Hg(0)). Recent laboratory and field studies have observed the reduction of Hg(II), but the chemical mechanism for this reaction has not been identified. Recent experimental work has shown that the reduction reaction is heterogeneous and can occur on iron and sodium chloride aerosol surfaces. This study explores the use of density functional theory calculations to discern the reduction pathways of HgCl2, HgBr2, Hg(NO3)2, and HgSO4 on clean Fe(110), NaCl(100), and NaCl(111)(Na) surfaces. Potential energy surfaces were prepared for the various reduction pathways, indicating that the reduction pathway leading to the production of gas-phase elemental mercury is highly favorable on Fe(110) and NaCl(111)(Na). Moreover, the Fe(110) surface requires an external energy source of ∼0.5 eV to desorb the reduced mercury, whereas the NaCl(111)(Na) surface requires no energy input. The results indicate that a number of mercury species can be reduced on metallic iron and sodium chloride surfaces, which are known aerosol components, and that a photochemical reaction involving the aerosol surface is likely needed for the reaction to be catalytic.