Colicin E5 specifically cleaves four tRNAs in Escherichia coli that contain the modified nucleotide queuosine (Q) at the wobble position, thereby preventing protein synthesis and ultimately resulting in cell death. Here, the crystal structure of the catalytic domain of colicin E5 (E5-CRD) from E. coli was determined at 1.5 A resolution. Unexpectedly, E5-CRD adopts a core folding with a four-stranded beta-sheet packed against an alpha-helix, seen in the well-studied ribonuclease T1 despite a lack of sequence similarity. Beyond the core catalytic domain, an N-terminal helix, a C-terminal beta-strand and loop, and an extended internal loop constitute an RNA binding cleft. Mutational analysis identified five amino acids that were important for tRNA substrate binding and cleavage by E5-CRD. The structure, together with the mutational study, allows us to propose a model of colicin E5-tRNA interactions, suggesting the molecular basis of tRNA substrate recognition and the mechanism of tRNA cleavage by colicin E5.