Gene regulation at the post-transcriptional level is prevalent in all domains of life. In bacteria, ProQ-like proteins have emerged as important RNA chaperones facilitating RNA stability and RNA duplex formation. In the major human pathogen V. cholerae, post-transcriptional gene regulation is key for virulence, biofilm formation, and antibiotic resistance, yet the role of ProQ has not been studied. Here, we show that ProQ interacts with hundreds of transcripts in V. cholerae, including the highly abundant FlaX small RNA (sRNA). Global analyses of RNA duplex formation using RIL-Seq (RNA interaction by ligation and sequencing) revealed a vast network of ProQ-assisted interactions and identified a role for FlaX in motility regulation. Specifically, FlaX base-pairs with multiple sites on the flaB flagellin mRNA, preventing 30S ribosome binding and translation initiation. V. cholerae cells lacking flaX display impaired motility gene expression, altered flagella composition, and reduced swimming in liquid environments. Our results provide a global view on ProQ-mediated RNA duplex formation and pinpoint the mechanistic and phenotypic consequences associated with ProQ-associated sRNAs in V. cholerae. Overall design: To investigate the RNA-RNA interactome on ProQ, V. cholerae WT and proQ-3XFLAG were cultivated in LB medium to OD600 of 0.2 and 2.0. Cells were subjected to RNA crosslinking, coimmunoprecipitation and ligation followed by chimeric cDNA synthesis and high-throughput sequencing. Two biological replicates for each condition are provided.