As the most ancient metazoan, sponges have established close relationships with particular microbial symbionts. However, the characteristics and physiology of thioautotrophic symbionts in deep-sea sponges are largely unknown. Using a tailored “differential coverage binning” method on 22-Gb metagenomic sequences, we recovered the nearly complete genome of a sulfur-oxidizing bacterium (SOB) that dominates the microbiota of the cold seep sponge Suberites sp. Phylogenetic analyses suggested that this bacterium (an unclassified gammaproteobacterium termed “Gsub”) may represent a new deep-sea SOB group. Microscopic observations suggest that Gsub is probably an extracellular symbiont. Gsub has complete sulfide oxidation and carbon fixation pathways, suggesting a chemoautotrophic lifestyle. Comparative genomics with other sponge-associated SOB and free-living SOB revealed significant genome reduction in Gsub, characterized by the loss of genes for carbohydrate metabolism, motility, DNA repair, and osmotic stress response. Intriguingly, this scenario of genome reduction is highly similar to those of the endosymbionts in deep-sea clams. However, Gsub has retained genes for phage defense and protein secretion, with the latter potentially playing a role in interactions with the sponge host. In addition, we recovered the genome of an ammonia-oxidizing archaeon (AOA), which may carry out ammonia oxidation and carbon fixation within the sponge body.