The toxic metalloid arsenic has been environmentally ubiquitous since life first arose nearly four billion years ago and presents a challenge for the survival of all living organisms. Its bioavailability has varied dramatically over the history of life on Earth. As life spread, biogeochemical and climate changes cyclically increased and decreased bioavailable arsenic. To elucidate the history of arsenic adaptation across the tree of life, we reconstructed the phylogeny of the arsM gene that encodes the As(III) S-adenosylmethionine (SAM) methyltransferase. Our results suggest that life successfully moved into arsenic-rich environments in the late Archean Eon and Proterozoic Eon, respectively, by the spread of arsM genes. The arsM genes of bacterial origin have been transferred to other kingdoms of life on at least six occasions, and the resulting domesticated arsM genes promoted adaptation to environmental arsenic. These results allow us to peer into the history of arsenic adaptation of life on our planet and imply that dissemination of genes encoding diverse adaptive functions to toxic chemicals permit adaptation to changes in concentrations of environmental toxins over evolutionary history.