Vibrio cholerae, the causative agent of cholera, requires iron for growth. One mechanism by which it acquires iron is the uptake of heme, and several heme utilization genes have been identified in V. cholerae. These include three distinct outer membrane receptors, two TonB systems, and an apparent ABC transporter to transfer heme across the inner membrane. However, little is known about the fate of the heme after it enters the cell. In this report we show that a novel heme utilization protein, HutZ, is required for optimal heme utilization. hutZ (open reading frame [ORF] VCA0907) is encoded with two other genes, hutW (ORF VCA0909) and hutX (ORF VCA0908), in an operon divergently transcribed from the tonB1 operon. A hutZ mutant grew poorly when heme was provided as the sole source of iron, and the poor growth was likely due to the failure to use heme efficiently as a source of iron, rather than to heme toxicity. Heme oxygenase mutants of both Corynebacterium diphtheriae and C. ulcerans fail to use heme as an iron source. When the hutWXZ genes were expressed in the heme oxygenase mutants, growth on heme was restored, and hutZ was required for this effect. Biochemical characterization indicated that HutZ binds heme with high efficiency; however, no heme oxygenase activity was detected for this protein. HutZ may act as a heme storage protein, and it may also function as a shuttle protein that increases the efficiency of heme trafficking from the membrane to heme-containing proteins.