A modified base at the first (wobble) position of some tRNA anticodons is critical for deciphering the genetic code. In eukaryotes and eubacteria, AUA codons are decoded by tRNAsIle with modified bases pseudouridine (and/or inosine) and lysidine, respectively. The mechanism by which archaeal species translate AUA codons is unclear. We describe a polyamine-conjugated modified base, 2-agmatinylcytidine (agm²C or agmatidine), at the wobble position of archaeal tRNA^Ile that decodes AUA codons specifically. We demonstrate that archaeal cells use agmatine to synthesize agm²C of tRNA^Ile. We also identified a new enzyme, tRNA^Ile-agm²C synthetase (TiaS), that catalyzes agm²C formation in the presence of agmatine and ATP. Although agm²C is chemically similar to lysidine, TiaS constitutes a distinct class of enzyme from tRNA^Ile-lysidine synthetase (TilS), suggesting that the decoding systems evolved convergently across domains.