Inactivation of the Pseudomonas aeruginosa (PAO1) hfq gene, encoding the Sm-like Hfq protein, resulted in pleiotropic effects that included an attenuated virulence. As regulation by Hfq often involves the action of small regulatory RNAs (sRNAs), we have used a shotgun cloning approach (RNomics) and bioinformatic tools to identify sRNAs in strain PAO1. For cDNA library construction, total RNA was extracted from PAO1 cultures either grown to stationary phase or exposed to human serum. The cDNA libraries were generated from small-sized RNAs of PAO1 after co-immunoprecipitation with Hfq. Of 400 sequenced cDNA clones, 11 mapped to intergenic regions. Band-shift assays and Northern blot analyses performed with two selected sRNAs confirmed that Hfq binds to and affects the steady-state levels of these RNAs. A proteome study performed upon overproduction of one sRNA, PhrS, implicated it in riboregulation. PhrS contains an ORF, and evidence for its translation is presented. In addition, based on surveys with structure-based bioinformatic tools, we provide an electronic compilation of putative sRNA and non-coding RNA genes of PAO1 based on their evolutionarily conserved structure.