The eukaryotic and archaeal translation factor IF5A requires a post-translational hypusine modification, which is catalyzed by deoxyhypusine synthase (DHS) at a single lysine residue of IF5A with NAD+ and spermidine as cofactors, followed by hydroxylation to form hypusine. While human DHS catalyzed reactions have been well characterized, the mechanism of the hypusination of archaeal IF5A by DHS is not clear. Here we report a DHS structure from Pyrococcus horikoshii OT3 (PhoDHS) at 2.2 Å resolution. The structure reveals two states in a single functional unit (tetramer): two NAD+-bound monomers with the NAD+ and spermidine binding sites observed in multi-conformations (closed and open), and two NAD+-free monomers. The dynamic loop region V288–P299, in the vicinity of the active site, adopts different positions in the closed and open conformations and is disordered when NAD+ is absent. Combined with NAD+ binding analysis, it is clear that PhoDHS can exist in three states: apo, PhoDHS-2 equiv NAD+, and PhoDHS-4 equiv NAD+, which are affected by the NAD+ concentration. Our results demonstrate the dynamic structure of PhoDHS at the NAD+ and spermidine binding site, with conformational changes that may be the response to the local NAD+ concentration, and thus fine-tune the regulation of the translation process via the hypusine modification of IF5A.