Deoxyhypusine hydroxylase (DOHH) catalyzes the final step in the post-translational synthesis of hypusine (N(epsilon)-(4-amino-2-hydroxybutyl)lysine) in eIF5A. DOHH is a HEAT-repeat protein with eight tandem helical hairpins in a symmetrical dyad. It contains two potential iron coordination sites (one on each dyad) composed of two strictly conserved His-Glu motifs. The purified human recombinant DOHH was a mixture of active holoenzyme containing 2 mol of iron/mol of DOHH and inactive metal-free apoenzyme. The two species could be distinguished by their different mobilities upon native gel electrophoresis. The DOHH apoenzyme exhibited markedly reduced levels of iron and activity. DOHH activity could be restored only by the addition of Fe2+ to the apoenzyme but not by other metals including Cd2+,Co2+,Cr2+,Cu2+,Mg2+,Mn2+,Ni2+, and Zn2+. The role of the strictly conserved His-Glu residues was evaluated by site-directed mutagenesis. Substitution of any single amino acid in the four His-Glu motifs with alanine abolished the enzyme activity. Of these eight alanine substitutions, six, including H56A, H89A, E90A, H207A, H240A, and E241A, caused a severe reduction in the iron content. Our results provide strong evidence that Fe(II) is the active-site-bound metal critical for DOHH catalysis and that the strictly conserved His-Glu motifs are essential for iron binding and catalysis. Furthermore, the iron to DOHH stoichiometry and dependence of iron binding on each of the four conserved His-Glu motifs suggest a binuclear iron mediated reaction mechanism, distinct from that of other Fe(II)-dependent protein hydroxylases, such as prolyl 4-hydroxylase or lysyl hydroxylases.