Glutaminyl-tRNA synthetase and asparaginyl-tRNA synthetase evolved from glutamyl-tRNA synthetase and aspartyl-tRNA synthetase, respectively, after the split in the last universal communal ancestor (LUCA). Glutaminyl-tRNA(Gln) and asparaginyl-tRNA(Asn) were likely formed in LUCA by amidation of the mischarged species, glutamyl-tRNA(Gln) and aspartyl-tRNA(Asn), by tRNA-dependent amidotransferases, as is still the case in most bacteria and all known archaea. The amidotransferase GatCAB is found in both domains of life, while the heterodimeric amidotransferase GatDE is found only in Archaea. The GatB and GatE subunits belong to a unique protein family that includes Pet112 that is encoded in the nuclear genomes of numerous eukaryotes. GatE was thought to have evolved from GatB after the emergence of the modern lines of decent. Our phylogenetic analysis though places the split between GatE and GatB, prior to the phylogenetic divide between Bacteria and Archaea, and Pet112 to be of mitochondrial origin. In addition, GatD appears to have emerged prior to the bacterial-archaeal phylogenetic divide. Thus, while GatDE is an archaeal signature protein, it likely was present in LUCA together with GatCAB. Archaea retained both amidotransferases, while Bacteria emerged with only GatCAB. The presence of GatDE has favored a unique archaeal tRNA(Gln) that may be preventing the acquisition of glutaminyl-tRNA synthetase in Archaea. Archaeal GatCAB, on the other hand, has not favored a distinct tRNA(Asn), suggesting that tRNA(Asn) recognition is not a major barrier to the retention of asparaginyl-tRNA synthetase in many Archaea.