Abstract Background As in eukaryotes, precursor transfer RNAs in Archaea often contain introns that are removed in tRNA maturation. Two unrelated archaeal species display unique pre-tRNA processing complexity in the form of split tRNA genes, in which two to three segments of tRNAs are transcribed from different loci, then trans-spliced to form a mature tRNA. Another rare type of pre-tRNA, found only in eukaryotic algae, is permuted, where the 3' half is encoded upstream of the 5' half, and must be processed to be functional. Results Using an improved version of the gene-finding program tRNAscan-SE, comparative analyses and experimental verifications, we have now identified four novel trans-spliced tRNA genes, each in a different species of the Desulfurococcales branch of the Archaea: tRNAAsp(GUC) in Aeropyrum pernix and Thermosphaera aggregans, and tRNALys(CUU) in Staphylothermus hellenicus and Staphylothermus marinus. Each of these includes features surprisingly similar to previously studied split tRNAs, yet comparative genomic context analysis and phylogenetic distribution suggest several independent, relatively recent splitting events. Additionally, we identified the first examples of permuted tRNA genes in Archaea: tRNAiMet(CAU) and tRNATyr(GUA) in Thermofilum pendens, which appear to be permuted in the same arrangement seen previously in red alga. Conclusions Our findings illustrate that split tRNAs are sporadically spread across a major branch of the Archaea, and that permuted tRNAs are a new shared characteristic between archaeal and eukaryotic species. The split tRNA discoveries also provide new clues to their evolutionary history, supporting hypotheses for recent acquisition via viral or other mobile elements.