Hydrogen sulfide (H2S) impairs mitochondrial respiration by potently inhibiting the heme-copper cytochrome c oxidase. Since many prokaryotes, including Escherichia (E.) coli, generate H2S and encounter high H2S levels particularly in the human gut, herein we tested whether bacteria can sustain sulfide-resistant O2-dependent respiration. E. coli has three respiratory oxidases, the cyanide-sensitive heme-copper bo3 enzyme and two bd oxidases much less sensitive to cyanide. Working on the isolated enzymes, we found that, whereas the bo3 oxidase is inhibited by sulfide with half-maximal inhibitory concentration IC50 = 1.1 ± 0.1 μM, under identical experimental conditions both bd oxidases are insensitive to sulfide up to 58 μM. In E. coli respiratory mutants, both O2-consumption and aerobic growth proved to be severely impaired by sulfide when respiration was sustained by the bo3 oxidase alone, but unaffected by ≤200 μM sulfide when either bd enzyme acted as the only terminal oxidase. Accordingly, wild-type E. coli showed sulfide-insensitive respiration and growth under conditions favouring the expression of bd oxidases. In all tested conditions, cyanide mimicked the functional effect of sulfide on bacterial respiration. We conclude that bd oxidases promote sulfide-resistant O2-consumption and growth in E. coli and possibly other bacteria. The impact of this discovery is discussed.