The biological oxidation of reduced sulfur compounds is a critically important process in global sulfur biogeochemistry. In this study, we enriched from marine sediments under denitrifying conditions, chemolithotrophic sulfur oxidizers that could oxidize a variety of reduced sulfur compounds: thiosulfate, tetrathionate, sulfide, and polysulfide. Two major phylotypes of 16S rRNA gene (>99% identity in each phylotype) were detected in this enrichment culture. In order to characterize sulfide oxidation, we sequenced and characterized one fosmid clone (43.6 kb) containing the group I sulfide-quinone reductase (sqr) gene. Interestingly, four putative rhodanese genes were found in this clone. Furthermore, comparative alignment with the closest genome of Thiomicrospira crunogena XCL2 revealed that three homologous genes were located within the vicinity of the sqr gene. Fosmid clones harboring carbon fixation (cbbL and cbbM) and denitrification (narG) genes were screened, and the phylogeny of the functional genes was analyzed. Along with the comparison between the sqr-containing fosmid clones and the relevant gamma-proteobacteria, our phylogenetic study based on the 16S rRNA gene and carbon fixation genes suggest the prevalence of chemolithotrophic gamma-proteobacteria in the denitrifying cultures. The findings of this study imply that a combination of cultivation and metagenomic approaches might provide us with a glimpse into the characteristics of sulfur oxidizers in marine sediments.