Predation by protists drives the evolution of defensive traits in bacteria, which may impact human disease. In this study, we conducted an experimental evolution study exposing the model human pathogen Vibrio cholerae to protist predation to understand the adaptive traits enabling environmental survival and fitness. The extended passage of V. cholerae through an amoeba host led to phenotypic and genotypic variability. Whole-genome sequencing identified diverse adaptive mutations in amoeba-adapted populations, including non-synonymous mutations in the flagellar transcriptional regulator, flrA. These mutations were associated with enhanced fitness, increased colonization of zebrafish, and improved survival inside the amoeba host. Further investigations of flrA mutants revealed increased pathogen growth and distinct transcriptomic changes during amoeba predation compared to the wild type. Transcriptome analysis highlighted up-regulation of genes involved in iron acquisition and amino acid biosynthesis in the absence of flrA. Additionally, the flrA mutants exhibited increased tolerance to oxidative stress, facilitated by catalases. Collectively, our findings elucidate how this bacterium adapts to protozoan predation, enhancing its resistance to environmental stresses and potential interactions with eukaryotic hosts.