Gene expression in mitochondria of kinetoplastid protozoa requires RNA editing, a post-transcriptional process which involves insertion or deletion of uridine residues at specific sites within mitochondrial pre-mRNAs. Sequence specificity of the RNA editing process is mediated by oligo-uridylated small, non-coding RNAs, designated as guide RNAs (gRNAs). In this study, we have analyzed the small ncRNA transcriptome from kinetoplast mitochondria of Leishmania tarentolae by generating specialized cDNA libraries encoding size-selected RNA species. Through this screen, a significant number of novel oligo-uridylated RNA species, which we have termed oU-RNAs, has been identified. Most novel oU-RNAs are present as stable RNA species in mitochondria as assessed by northern blot analysis. Thereby, novel oU-RNAs show similar expression levels and sizes as previously reported for canonical gRNAs. Several oU-RNAs are transcribed from both strands of the maxicircle and minicircles components of the mitochondrial genome, from regions where up till now no transcription has been reported. Two stable oU-RNAs exhibit an anchor sequence in antisense orientation to known gRNAs and thus might regulate editing of respective pre-mRNAs. A number of oU-RNAs map in antisense orientation to non-edited protein-coding genes suggesting that they might function by a different mechanism. In addition, our screen shows that all kinetoplast-derived RNAs are prone to some degree of uridylation.