All canonical transfer RNAs (tRNAs) have a uridine at position 8, involved in maintaining tRNA tertiary structure. However, the hyperthermophilic archaeon Methanopyrus kandleri harbors 30 (out of 34) tRNA genes with cytidine at position 8. Here, we demonstrate C-to-U editing at this location in the tRNA's tertiary core, and present the crystal structure of a tRNA-specific cytidine deaminase, CDAT8, which has the cytidine deaminase domain linked to a tRNA-binding THUMP domain. CDAT8 is specific for C deamination at position 8, requires only the acceptor stem hairpin for activity, and belongs to a unique family within the "cytidine deaminase-like" superfamily. The presence of this C-to-U editing enzyme guarantees the proper folding and functionality of all M. kandleri tRNAs.