Quorum sensing is a mechanism of cell-cell communication that bacteria use to control collective behaviours including bioluminescence, biofilm formation and virulence factor production. In the Vibrio harveyi and Vibrio cholerae quorum-sensing circuits, multiple non-coding small regulatory RNAs called the quorum-regulated small RNAs (Qrr sRNAs) function to establish the global quorum-sensing gene expression pattern by modulating translation of multiple mRNAs encoding quorum-sensing regulatory factors. Here we show that the Qrr sRNAs post-transcriptionally activate production of the low cell density master regulator AphA through base pairing to aphA mRNA, and this is crucial for the accumulation of appropriate levels of AphA protein at low cell density. We find that the Qrr sRNAs use unique pairing regions to discriminate between their different targets. Qrr1 is not as effective as Qrr2-5 in activating aphA because Qrr1 lacks one of two required pairing regions. However, Qrr1 is equally effective as the other Qrr sRNAs at controlling targets like luxR and luxO because it harbours all of the required pairing regions for these targets. Sequence comparisons reveal that Vibrionaceae species possessing only qrr1 do not have the aphA gene under Qrr sRNA control. Our findings suggest co-evolving relationships between particular Qrr sRNAs and particular mRNA targets.