To survive, many pathogens extract heme from their host organism and break down the porphyrin scaffold to sequester the Fe2+ ion via a heme oxygenase. Recent studies have revealed that certain pathogens can anaerobically degrade heme. Our own research has shown that one such pathway proceeds via NADH-dependent heme degradation, which has been identified in a family of hemoproteins from a range of bacteria. HemS, from Yersinia enterocolitica, is the main focus of this work, along with HmuS (Yersinia pestis), ChuS (Escherichia coli) and ShuS (Shigella dysenteriae). We combine experiments, Energy Landscape Theory, and a bioinformatic investigation to place these homologues within a wider phylogenetic context. A subset of these hemoproteins are known to bind certain DNA promoter regions, suggesting not only that they can catalytically degrade heme, but that they are also involved in transcriptional modulation responding to heme flux. Many of the bacterial species responsible for these hemoproteins (including those that produce HemS, ChuS and ShuS) are known to specifically target oxygen-depleted regions of the gastrointestinal tract. A deeper understanding of anaerobic heme breakdown processes exploited by these pathogens could therefore prove useful in the development of future strategies for disease prevention.