Sulfide (H2S, HS- and S2-) oxidation to sulfite and thiosulfate by heterotrophic bacteria, using sulfide:quinone oxidoreductase (SQR) and persulfide dioxygenase (PDO), has recently been reported as a possible detoxification mechanism for sulfide at high levels. Bioinformatic analysis revealed that the sqr and pdo genes were common in sequenced bacterial genomes, implying the sulfide oxidation may have other physiological functions. SQRs have previously been classified into six types. Here we grouped PDOs into three types and showed that some heterotrophic bacteria produced and released H2S from organic sulfur into the headspace during aerobic growth, and others, for example, Pseudomonas aeruginosa PAO1, with sqr and pdo did not release H2S. When the sqr and pdo genes were deleted, the mutants also released H2S. Both sulfide-oxidizing and non-oxidizing heterotrophic bacteria were readily isolated from various environmental samples. The sqr and pdo genes were also common in the published marine metagenomic and metatranscriptomic data, indicating that the genes are present and expressed. Thus, heterotrophic bacteria actively produce and consume sulfide when growing on organic compounds under aerobic conditions. Given their abundance on Earth, their contribution to the sulfur cycle should not be overlooked.