Small regulatory RNAs (sRNAs) are crucial components of many stress response systems. The envelope stress response (ESR) of Gram-negative bacteria is a paradigm for sRNA-mediated stress management and involves, among other factors, the alternative sigma factor E (σE ) and one or more sRNAs. In this study, we identified the MicV sRNA as a new member of the σE regulon in Vibrio cholerae. We show that MicV acts redundantly with another sRNA, VrrA, and that both sRNAs share a conserved seed-pairing domain allowing them to regulate multiple target mRNAs. V. cholerae lacking σE displayed increased sensitivity toward antimicrobials, and over-expression of either of the sRNAs suppressed this phenotype. Laboratory selection experiments using a library of synthetic sRNA regulators revealed that the seed-pairing domain of σE -dependent sRNAs is strongly enriched among sRNAs identified under membrane-damaging conditions and that repression of OmpA is crucial for sRNA-mediated stress relief. Together, our work shows that MicV and VrrA act as global regulators in the ESR of V. cholerae and provides evidence that bacterial sRNAs can be functionally annotated by their seed-pairing sequences.