Arsenic is a ubiquitous environmental toxic substance and a Class 1 human carcinogen. Arsenic methylation by the enzyme As(III) S-adenosylmethionine (SAM) methyltransferase (ArsM in microbes or AS3MT in animals) detoxifies As(III) in microbes but transforms it into more toxic and potentially more carcinogenic methylated species in humans. We previously proposed a reaction pathway for ArsM/AS3MT that involves initial 3-coordinate binding of As(III). To date, reported structures have had only 2-coordinately bound trivalent arsenicals. Here we report a crystal structure of CmArsM from Cyanidioschyzon sp.5508 in which As(III) is 3-coordinately bound to three conserved cysteine residues with a molecule of the product S-adenosyl-l-homocysteine bound in the SAM binding site. We propose that this structure represents the first step in the catalytic cycle. In a previously reported SAM-bound structure, a disulfide bond is formed between two conserved cysteine residues. Comparison of these two structures indicates that there is a conformational change in the N-terminal domain of CmArsM that moves a loop to allow formation of the 3-coordinate As(III) binding site. We propose that this conformational change is an initial step in the As(III) SAM methyltransferase catalytic cycle.