Limited oxygen availability is a prevalent problem in microbial biotechnology. Recombinant Escherichia coli expressing the hemoglobin from Vitreoscilla (VHb) or the flavohemoglobin from Ralstonia eutropha (formerly Alcaligenes eutrophus) (FHP) demonstrate significantly increased cell growth and productivity under microaerobic conditions. We identify novel bacterial hemoglobin-like proteins and examine if these novel bacterial hemoglobins can elicit positive effects similar to VHb and FHP and if these hemoglobins alleviate oxygen limitation under microaerobic conditions when expressed in E. coli. Several finished and unfinished bacterial genomes were screened using R. eutropha FHP as a query sequence for genes (hmp) encoding hemoglobin-like proteins. Novel hmp genes were identified in Pseudomonas aeruginosa, Salmonella typhi, Klebsiella pneumoniae, Deinococcus radiodurans, and Campylobacter jejuni. Previously characterized hmp genes from E. coli and Bacillus subtilis and the novel hmp genes from P. aeruginosa, S. typhi, C. jejuni, K. pneumoniae, and D. radiodurans were PCR amplified and introduced into a plasmid for expression in E. coli. Biochemically active hemoproteins were expressed in all constructs, as judged by the ability to abduct carbon monoxide. Growth behavior and byproduct formation of E. coli K-12 MG1655 cells expressing various hemoglobins were analyzed in microaerobic fed-batch cultivations and compared to plasmid-bearing control and to E. coli cells expressing VHb. The clones expressing hemoglobins from E. coli, D. radiodurans, P.aeruginosa, and S. typhi reached approximately 10%, 27%, 23%, and 36% higher final optical density values, respectively, relative to the plasmid bearing E. coli control (A(600) 5.5). E. coli cells expressing hemoproteins from P. aeruginosa, S. typhi, and D. radiodurans grew to similar final cell densities as did the strain expressing VHb (A(600) 7.5), although none of the novel constructs was able to outgrow the VHb-expressing E. coli strain. Additionally, increased yield of biomass on glucose was measured for all recombinant strains, and an approximately 2-fold yield enhancement was obtained with D. radiodurans hemoprotein-expressing E. coli relative to the E. coli control carrying the parental plasmid without any hemoglobin gene.