Eukaryotic eIF5A and its bacterial orthologue EF-P are translation elongation factors whose task is to rescue ribosomes from stalling during the synthesis of proteins bearing particular sequences such as polyproline stretches. Both proteins are characterized by unique post-translational modifications, hypusination and lysinylation, respectively, which are essential for their function. An orthologue is present in all Archaea but its function is poorly understood. Here, we show that aIF5A of the crenarchaeum Sulfolobus solfataricus is hypusinated and forms a stable complex with deoxyhypusine synthase, the first enzyme of the hypusination pathway. The recombinant enzyme is able to modify its substrate in vitro resulting in deoxyhypusinated aIF5A. Moreover, with the aim to identify the enzyme involved in the second modification step, i.e. hypusination, a set of proteins interacting with aIF5A was identified.