Computer analysis using profiles generated by the PSI-BLAST program identified a superfamily of proteins homologous to eukaryotic transglutaminases. The members of the new protein superfamily are found in all archaea, show a sporadic distribution among bacteria, and were detected also in eukaryotes, such as two yeast species and the nematode Caenorhabditis elegans. Sequence conservation in this superfamily primarily involves three motifs that center around conserved cysteine, histidine, and aspartate residues that form the catalytic triad in the structurally characterized transglutaminase, the human blood clotting factor XIIIa′. On the basis of the experimentally demonstrated activity of the Methanobacterium phage pseudomurein endoisopeptidase, it is proposed that many, if not all, microbial homologs of the transglutaminases are proteases and that the eukaryotic transglutaminases have evolved from an ancestral protease.