Heme catabolism is an important biochemical process that many bacterial pathogens utilize to acquire iron. However, tetrapyrrole catabolites can be reactive and often require further processing for transport out of the cell or conversion to another useful cofactor. In previous work, we presented in vitro evidence of an anaerobic heme degradation pathway in Escherichia coli O157:H7. Consistent with reactions that have been reported for other radical S-adenosyl-l-methionine methyltransferases, ChuW transfers a methyl group to heme by a radical-mediated mechanism and catalyzes the β-scission of the porphyrin macrocycle. This facilitates iron release and the production of a new linear tetrapyrrole termed "anaerobilin". In this work, we describe the structure and function of ChuY, an enzyme expressed downstream from chuW within the same heme utilization operon. ChuY is structurally similar to biliverdin reductase and forms a dimeric complex in solution that reduces anaerobilin to the product we have termed anaerorubin. Steady state analysis of ChuY exhibits kinetic cooperativity that is best explained by a random addition mechanism with a kinetically preferred path for initial reduced nicotinamide adenine dinucleotide phosphate binding.