A critical step in the biogeochemical cycle of sulfur on Earth is microbial sulfate reduction, yet organisms from relatively few lineages have been implicated in this process. Previous studies using functional marker genes have detected abundant, novel dissimilatory sulfite reductases (DsrAB) that could confer the capacity for microbial sulfite/sulfate reduction but were not affiliated with known organisms. Thus, the identity of a significant fraction of sulfate/sulfite-reducing microbes has remained elusive. Here we report the discovery of the capacity for sulfate/sulfite reduction in the genomes of organisms from 13 bacterial and archaeal phyla, thereby more than doubling the number of microbial phyla associated with this process. Eight of the 13 newly identified groups are candidate phyla that lack isolated representatives, a finding only possible given genomes from metagenomes. Organisms from Verrucomicrobia and two candidate phyla, Candidatus Rokubacteria and Candidatus Hydrothermarchaeota, contain some of the earliest evolved dsrAB genes. The capacity for sulfite reduction has been laterally transferred in multiple events within some phyla, and a key gene potentially capable of modulating sulfur metabolism in associated cells has been acquired by putatively symbiotic bacteria. We conclude that current functional predictions based on phylogeny significantly underestimate the extent of sulfate/sulfite reduction across Earth’s ecosystems. Understanding the prevalence of this capacity is integral to interpreting the carbon cycle because sulfate reduction is often coupled to turnover of buried organic carbon. Our findings expand the diversity of microbial groups associated with sulfur transformations in the environment and motivate revision of biogeochemical process models based on microbial community composition.