Glutaminyl-transfer RNA (Gln-tRNA(Gln)) in archaea is synthesized in a pretranslational amidation of misacylated Glu-tRNA(Gln) by the heterodimeric Glu-tRNA(Gln) amidotransferase GatDE. Here we report the crystal structure of the Methanothermobacter thermautotrophicus GatDE complexed to tRNA(Gln) at 3.15 Å resolution. Biochemical analysis of GatDE and of tRNA(Gln) mutants characterized the catalytic centers for the enzyme's three reactions (glutaminase, kinase, and amidotransferase activity). A 40 angstrom-long channel for ammonia transport connects the active sites in GatD and GatE. tRNA(Gln) recognition by indirect readout based on shape complementarity of the D loop suggests an early anticodon-independent RNA-based mechanism for adding glutamine to the genetic code.