CCA-adding enzymes polymerize CCA onto the 3′ terminus of immature tRNAs without using a nucleic acid template. The 3.0 Å resolution crystal structures of the CCA-adding enzyme from Bacillus stearothermophilus and its complexes with ATP or CTP reveal a seahorse-shaped subunit consisting of four domains: head, neck, body, and tail. The head is structurally homologous to the palm domain of DNA polymerase β but has additional structural features and functions. The neck, body, and tail represent new protein folding motifs. The neck provides a specific template for the incoming ATP or CTP, whereas the body and tail may bind tRNA. Each subunit has one active site capable of switching its base specificity between ATP and CTP, an important component of the CCA-adding mechanism.