Heme-degrading enzymes are involved in human diseases ranging from stroke, cancer, and multiple sclerosis to infectious diseases such as malaria, diphtheria, and meningitis. All mammalian and microbial enzymes identified to date are members of the heme oxygenase superfamily and assume similar monomeric structures with an all alpha-helical fold. Here we describe the crystal structures of IsdG and IsdI, two heme-degrading enzymes from Staphylococcus aureus. The structures of both enzymes resemble the ferredoxin-like fold and form a beta-barrel at the dimer interface. Two large pockets found on the outside of the barrel contain the putative active sites. Sequence homologs of IsdG and IsdI were identified in multiple Gram-positive pathogens. Substitution of conserved IsdG amino acid residues either reduced or abolished heme degradation, suggesting a common catalytic mechanism. This mechanism of IsdG-mediated heme degradation may be similar to that of the structurally related monooxygenases, enzymes involved in the synthesis of antibiotics in Streptomyces. Our results imply the evolutionary adaptation of microbial enzymes to unique environments.