The opportunistic pathogen Pseudomonas aeruginosa PAO1 has a remarkable capacity to adapt to various environments and to survive with limited nutrients. Here, we report the discovery and characterization of a novel small non-coding RNA: NrsZ (nitrogen-regulated sRNA). We show that under nitrogen limitation, NrsZ is induced by the NtrB/C two component system, an important regulator of nitrogen assimilation and P. aeruginosa's swarming motility, in concert with the alternative sigma factor RpoN. Furthermore, we demonstrate that NrsZ modulates P. aeruginosa motility by controlling the production of rhamnolipid surfactants, virulence factors notably needed for swarming motility. This regulation takes place through the post-transcriptional control of rhlA, a gene essential for rhamnolipids synthesis. Interestingly, we also observed that NrsZ is processed in three similar short modules, and that the first short module encompassing the first 60 nucleotides is sufficient for NrsZ regulatory functions.