Cytoplasmic terminal uridylyl transferases comprise a conserved family of enzymes that negatively regulate the stability or biological activity of a variety of eukaryotic RNAs, including mRNAs and tumor-suppressor let-7 microRNAs. Here we describe crystal structures of the Schizosaccharomyces pombe cytoplasmic terminal uridylyl transferase Cid1 in two apo conformers and bound to UTP. We demonstrate that a single histidine residue, conserved in mammalian Cid1 orthologs, is responsible for discrimination between UTP and ATP. We also describe a new high-affinity RNA substrate-binding mechanism of Cid1, which is essential for enzymatic activity and is mediated by three basic patches across the surface of the enzyme. Overall, our structures provide a basis for understanding the activity of Cid1 and a mechanism of UTP selectivity conserved in its human orthologs, suggesting potential implications for anticancer drug design.