Pseudomonas aeruginosa is a highly adaptable bacterium that thrives in a broad range of ecological niches and can infect multiple hosts as diverse as plants, nematodes and mammals. In humans, it is an important opportunistic pathogen. This wide adaptability correlates with its broad genetic diversity. In this study, we used a deep-sequencing approach to explore the complement of small RNAs (sRNAs) in P. aeruginosa as the number of such regulatory molecules previously identified in this organism is relatively low, considering its genome size, phenotypic diversity and adaptability. We have performed a comparative analysis of PAO1 and PA14 strains which share the same host range but differ in virulence, PA14 being considerably more virulent in several model organisms. Altogether, we have identified more than 150 novel candidate sRNAs and validated a third of them by Northern blotting. Interestingly, a number of these novel sRNAs are strain-specific or showed strain-specific expression, strongly suggesting that they could be involved in determining specific phenotypic traits.