The sole gain of laterally acquired virulence genes does not fully explain the transition of environmental strains into human pathogens. To date, the specific molecular drivers and fitness trade-offs that enable some strains within a population to undergo this process remain enigmatic. Here, we describe a small RNA (sRNA) with a unique modular structure that shapes the evolution of toxigenic Vibrio cholerae , the agent of cholera. The sRNA comprises of a highly variable 5’ module located within the ompU ORF and a conserved 3’ one downstream from the gene. This atypical location confers a distinct bimodular structure to the OmpU-encoded sRNA (OueS), generating allelic variants that differentially contribute to the emergence of virulence potential in some strains and associated fitness trade-offs between human infection and environmental survival. Unlike environmental counterparts, the OueS allele from toxigenic strains controls phenotypes essential during host colonization: a) stringently inhibits biofilm formation via a novel sRNA-sRNA interaction by suppressing the iron-responsive sRNA RyhB, and b) confers resistance against intestinal bacteriophages by activating the recently discovered CBASS phage defense system. Toxigenic OueS is also required for successful intestinal colonization and, as the first known example of its kind, acts as a functional surrogate of the master virulence regulator ToxR, controlling over 84% of its regulome. On the other hand, isogenic strains encoding environmental alleles of OueS exhibit higher competitive fitness than those harboring toxigenic ones during colonization of natural reservoirs such as crustaceans and phytoplankton. Our findings provide critical insights into the evolution of toxigenic V. cholerae and reveal specific molecular mechanisms and fitness costs associated with the emergence of pathogenic traits in bacteria.