Pyridoxal-5'-phosphate-dependent cysteine desulfurase (IscS) is an essential enzyme in the assembly of FeS clusters in bacteria as well as in the mitochondria of eukaryotes. Although FeS proteins are particularly important for the energy metabolism of amitochondrial anaerobic eukaryotes, there is no information about FeS cluster formation in these organisms. We identified and sequenced two IscS homologs of Trichomonas vaginalis (TviscS-1 and TviscS-2) and one of Giardia intestinalis (GiiscS). TviscS-1, TviscS-2, and GiiscS possess the typical conserved regions implicated in cysteine desulfurase activity. N-termini of TviscS-1 and TviscS-2 possess eight amino acid extensions, which resemble the N-terminal presequences that target proteins to hydrogenosomes in trichomonads. No presequence was evident in GiiscS from Giardia, an organism that apparently lacks hydrogenosmes or mitochondria. Phylogenetic analysis showed a close relationship among all eukaryotic IscS genes including those of amitochondriates. IscS of proteobacteria formed a sister group to the eukaryotic clade, suggesting that isc-related genes were present in the proteobacterial endosymbiotic ancestor of mitochondria and hydrogenosomes. NifS genes of nitrogen-fixing bacteria, which are IscS homologs required for specific formation of FeS clusters in nitrogenase, formed a more distant group. The phylogeny indicates the presence of a common mechanism for FeS cluster formation in mitochondriates as well as in amitochondriate eukaryotes. Furthermore, the analyses support a common origin of Trichomonas hydrogenosomes and mitochondria, as well as secondary loss of mitochondrion/hydrogenosome-like organelles in Giardia.