Microbial arsenic (As) methylation and volatilization are important processes controlling the As biogeochemical cycle in paddy soils. To further understand these processes, we isolated a novel bacterial strain, SM-1, from an As-contaminated paddy soil. SM-1 showed strong As methylation and volatilization abilities, converting almost all arsenite (10 μM) to dimethylarsenate and trimethylarsenic oxide in the medium and trimethylarsine gas into the headspace within 24 h, with trimethylarsine accounting for nearly half of the total As. On the basis of the 16S rRNA sequence, strain SM-1 represents a new species in a new genus within the family Cytophagaceae. Strain SM-1 is abundant in the paddy soil and inoculation of SM-1 greatly enhanced As methylation and volatilization in the soil. An arsenite methyltransferase gene (ArarsM) was cloned from SM-1. When expressed in Escherichia coli, ArArsM conferred the As methylation and volatilization abilities to E. coli and increased its resistance to arsenite. The high As methylation and volatilization abilities of SM-1 are likely attributed to an efficient ArArsM enzyme coupled with low arsenite efflux. These results suggest that strain SM-1 plays an important role in As methylation and volatilization in the paddy soil and has a great potential for As bioremediation.