Quorum sensing, a cell-to-cell communication system based on small signal molecules, is employed by the human pathogen Pseudomonas aeruginosa to regulate virulence and biofilm development. Moreover, regulation by small trans-encoded RNAs has become a focal issue in studies of virulence gene expression of bacterial pathogens. In this study, we have identified the small RNA PhrS as an activator of PqsR synthesis, one of the key quorum-sensing regulators in P. aeruginosa. Genetic studies revealed a novel mode of regulation by a sRNA, whereby PhrS uses a base-pairing mechanism to activate a short upstream open reading frame to which the pqsR gene is translationally coupled. Expression of phrS requires the oxygen-responsive regulator ANR. Thus, PhrS is the first bacterial sRNA that provides a regulatory link between oxygen availability and quorum sensing, which may impact on oxygen-limited growth in P. aeruginosa biofilms.