The hydrogenase in Azotobacter vinelandii, like other membrane-bound [NiFe] hydrogenases, consists of a catalytic heterodimer and an integral membrane cytochrome b. The histidines ligating the hemes in this cytochrome b were identified by H₂ oxidation properties of altered proteins produced by site-directed mutagenesis. Four fully conserved and four partially conserved histidines in HoxZ were substituted with alanine or tyrosine. The roles of these histidines in HoxZ heme binding and hydrogenase were characterized by O₂-dependent H₂ oxidation and H₂-dependent methylene blue reduction in vivo. Mutants H33A/Y (H33 replaced by A or Y), H74A/Y, H194A, H208A/Y, and H194,208A lost O₂-dependent H₂ oxidation activity, H194Y and H136A had partial activity, and H97Y,H98A and H191A had full activity. These results suggest that the fully conserved histidines 33, 74, 194, and 208 are ligands to the hemes, tyrosine can serve as an alternate ligand in position 194, and H136 plays a role in H₂ oxidation. In mutant H194A/Y, imidazole (Imd) rescued H₂ oxidation activity in intact cells, which suggests that Imd acts as an exogenous ligand. The heterodimer activity, quantitatively determined as H₂-dependent methylene blue reduction, indicated that the heterodimers of all mutants were catalytically active. H33A/Y had wild-type levels of methylene blue reduction, but the other HoxZ ligand mutants had significantly less than wild-type levels. Imd reconstituted full methylene blue reduction activity in mutants H194A/Y and H208A/Y and partial activity in H194,208A. These results indicate that structural and functional integrity of HoxZ is required for physiologically relevant H₂ oxidation, and structural integrity of HoxZ is necessary for full heterodimer-catalyzed H₂ oxidation.