Both hydrogen sulfide (H2S) and methyl mercaptan (CH3SH) are frequently detected in large amounts in malodorous mouth air. We investigated the bacterial composition of saliva of 30 subjects with severe oral malodor exhibiting extreme CH3SH/H2S ratios (high H2S but low CH3SH concentrations, n = 14; high CH3SH but low H2S concentrations, n = 16) and 13 subjects without malodor, using barcoded pyrosequencing analysis of the 16S rRNA gene. Phylogenetic community analysis with the UniFrac distance metric revealed a distinct bacterial community structure in each malodor group. The H2S group showed higher proportions of the genera Neisseria, Fusobacterium, Porphyromonas and SR1 than the other two groups, whereas the CH3SH group had higher proportions of the genera Prevotella, Veillonella, Atopobium, Megasphaera, and Selenomonas. Our results suggested that distinct bacterial populations in the oral microbiota are involved in production of high levels of H2S and CH3SH in the oral cavity.