Arsenosugars are arsenic-containing ribosides that play a substantial role in arsenic biogeochemical cycles. Arsenosugars were identified more than 30 years ago, and yet their mechanism of biosynthesis remains unknown. In this study we report identification of the arsS gene from the cyanobacterium Synechocystis sp. PCC 6803 and show that it is involved in arsenosugar biosynthesis. In the Synechocystis sp. PCC 6803 ars operon, arsS is adjacent to the arsM gene that encodes an As(III) S-adenosylmethionine (SAM) methyltransferase. The gene product, ArsS, contains a characteristic CX3CX2C motif which is typical for the radical SAM superfamily. The function of ArsS was identified from a combination of arsS disruption in Synechocystis sp. PCC 6803 and heterologous expression of arsM and arsS in Escherichia coli. Both genes are necessary, indicating a multistep pathway of arsenosugar biosynthesis. In addition, we demonstrate that ArsS orthologs from three other freshwater cyanobacteria and one picocyanobacterium are involved in arsenosugar biosynthesis in those microbes. This study represents the identification of the first two steps in the pathway of arsenosugar biosynthesis. Our discovery expands the catalytic repertoire of the diverse radical SAM enzyme superfamily and provides a basis for studying the biogeochemistry of complex organoarsenicals.