Quorum sensing is a chemical communication process that bacteria use to control collective behaviours including bioluminescence, biofilm formation, and virulence factor production. In Vibrio harveyi, five homologous small RNAs (sRNAs) called Qrr1-5, control quorum-sensing transitions. Here, we identify 16 new targets of the Qrr sRNAs. Mutagenesis reveals that particular sequence differences among the Qrr sRNAs determine their target specificities. Modelling coupled with biochemical and genetic analyses show that all five of the Qrr sRNAs possess four stem-loops: the first stem-loop is crucial for base pairing with a subset of targets. This stem-loop also protects the Qrr sRNAs from RNase E-mediated degradation. The second stem-loop contains conserved sequences required for base pairing with the majority of the target mRNAs. The third stem-loop plays an accessory role in base pairing and stability. The fourth stem-loop functions as a rho-independent terminator. In the quorum-sensing regulon, Qrr sRNAs-controlled genes are the most rapid to respond to quorum-sensing autoinducers. The Qrr sRNAs are conserved throughout vibrios, thus insights from this work could apply generally to Vibrio quorum sensing.