The presence of the 7-deazaguanosine derivative archaeosine (G(+)) at position 15 in tRNA is one of the diagnostic molecular characteristics of the Archaea. The biosynthesis of this modified nucleoside is especially complex, involving the initial production of 7-cyano-7-deazaguanine (preQ(0)), an advanced precursor that is produced in a tRNA-independent portion of the biosynthesis, followed by its insertion into the tRNA by the enzyme tRNA-guanine transglycosylase (arcTGT), which replaces the target guanine base yielding preQ(0)-tRNA. The enzymes responsible for the biosynthesis of preQ(0) were recently identified, but the enzyme(s) catalyzing the conversion of preQ(0)-tRNA to G(+)-tRNA have remained elusive. Using a comparative genomics approach, we identified a protein family implicated in the late stages of archaeosine biosynthesis. Notably, this family is a paralog of arcTGT and is generally annotated as TgtA2. Structure-based alignments comparing arcTGT and TgtA2 reveal that TgtA2 lacks key arcTGT catalytic residues and contains an additional module. We constructed a Haloferax volcanii DeltatgtA2 derivative and demonstrated that tRNA from this strain lacks G(+) and instead accumulates preQ(0). We also cloned the corresponding gene from Methanocaldococcus jannaschii (mj1022) and characterized the purified recombinant enzyme. Recombinant MjTgtA2 was shown to convert preQ(0)-tRNA to G(+)-tRNA using several nitrogen sources and to do so in an ATP-independent process. This is the only example of the conversion of a nitrile to a formamidine known in biology and represents a new class of amidinotransferase chemistry.