Maturation of the tRNA 3' terminus is a complicated process in bacteria. Usually, it is initiated by an endonucleolytic cleavage carried out by RNase E and Z in different bacteria. In Escherichia coli, RNase E cleaves AU-rich sequences downstream of tRNA, producing processing intermediates with a few extra residues at the 3' end; these are then removed by exoribonuclease trimming to generate the mature 3' end. Here we show that essentially all E. coli tRNA precursors contain a potential RNase E cleavage site, the AU-rich sequence element (AUE), in the 3' trailer. This suggests that RNase E cleavage and exonucleolytic trimming is a general pathway for tRNA maturation in this organism. Remarkably, the AUE immediately downstream of each tRNA is selectively conserved in bacteria having RNase E and tRNA-specific exoribonucleases, suggesting that this pathway for tRNA processing is also commonly used in these bacteria. Two types of RNase E-like proteins are identified in actinobacteria and the alpha-subdivision of proteobacteria. The tRNA 3' proximal AUE is conserved in bacteria with only one type of E-like protein. Selective conservation of the AUE is usually not observed in bacteria without RNase E. These results demonstrate a novel example of co-evolution of RNA sequences with processing activities.