Rapid temperature rise in Arctic permafrost impacts not only the degradation of stored soil organic carbon (SOC) and climate feedback, but also the production and bioaccumulation of methylmercury (MeHg) toxin that can endanger humans, as well as wildlife in terrestrial and aquatic ecosystems. Currently little is known concerning the effects of rapid permafrost thaw on microbial methylation and how SOC degradation is coupled to MeHg biosynthesis. Here we describe the effects of warming on MeHg production in an Arctic soil during an 8-month anoxic incubation experiment. Net MeHg production increased >10 fold in both organic- and mineral-rich soil layers at warmer (8 °C) than colder (-2 °C) temperatures. The type and availability of labile SOC, such as reducing sugars and ethanol, were particularly important in fueling the rapid initial biosynthesis of MeHg. Freshly amended mercury was more readily methylated than preexisting mercury in the soil. Additionally, positive correlations between mercury methylation and methane and ferrous ion production indicate linkages between SOC degradation and MeHg production. These results show that climate warming and permafrost thaw could potentially enhance MeHg production by an order of magnitude, impacting Arctic terrestrial and aquatic ecosystems by increased exposure to mercury through bioaccumulation and biomagnification in the food web.