Bacterial small regulatory RNAs (sRNAs) are known to have regulatory functions in a variety of processes including metabolic reactions, stress responses and pathogenesis in response to environmental signals. Recent genome-wide studies to identify sRNAs have been largely based on tiling arrays and RNA sequencing (RNAseq) technologies. The latter approach, in particular, has revolutionized sRNA discovery by enabling interrogation of the transcriptome at unprecedented depths. The size and complexity of the P. aeruginosa genome suggests that it encodes many hitherto undetected sRNAs. In this study, RNA-seq is used to identify sRNAs in P.aeruginosa using a combination of three different sequencing libraries. Over 750 novel sRNAs (including intergenic and cis-encoded sRNAs) have been identified with this approach in this study. The results also reflect that although the use of three libraries increased the number of novel transcripts identified, there were significant differences in the subset of transcripts detected in each library, underscoring the importance of library preparation strategy and relative sRNA abundance for successful sRNA detection. These data will be useful for the study of regulatory sRNAs in P. aeruginosa and the approach described here may be applied to identify sRNAs in any bacterium under different growth and stress conditions. In addition the role of sRNA OsiS was investigated. OsiS was identified in our genome-wide search of sRNAs in P. aeruginosa. OsiS is highly transcribed during oxidative stress conditions. We show that by inducing the expression of OsiS the levels of the sRNA PhrS are greatly reduced. PhrS activates the translation of the pqsR gene under low oxygen concentrations, which in turn activates the synthesis of the Pseudomonas quinolone signal (PQS). Thus, OsiS links the oxygen levels to the production of quorum sensing (QS) molecules. It is hypothesized that the interaction is by direct base-pairing between the two sRNAs, with a predicted recognition site of OsiS at the highly conserved-region of PhrS. However, more experiments are required to know the exact nature of the interaction between these two sRNAs. Notably, OsiS is, to the best of our knowledge, the first sRNA whose main function seems to be regulating the cellular levels of another sRNA.