Organisms have evolved the ability to tolerate toxic substances in their environments, often by producing metabolic enzymes that efficiently detoxify the toxicant. Inorganic arsenic is one of the most toxic and carcinogenic substances in the environment, but many organisms, including humans, metabolise inorganic arsenic to less toxic metabolites. This multistep process produces mono-, di-, and trimethylated arsenic metabolites, which the organism excretes. In humans, arsenite methyltransferase (AS3MT) appears to be the main metabolic enzyme that methylates arsenic. In this study, we examined the evolutionary origin of AS3MT and assessed the ability of different genotypes to produce methylated arsenic metabolites. Phylogenetic analysis suggests that multiple, independent horizontal gene transfers between different bacteria, and from bacteria to eukaryotes, increased tolerance to environmental arsenic during evolution. These findings are supported by the observation that genetic variation in AS3MT correlates with the capacity to methylate arsenic. Adaptation to arsenic thus serves as a model for how organisms evolve to survive under toxic conditions.