The opportunistic pathogen Pseudomonas aeruginosa is ubiquitous in the environment, and in humans, it is capable of causing acute or chronic infections. In the natural environment, predation by bacterivorous protozoa represents a primary threat to bacteria. Here, we determined the impact of long-term exposure of P. aeruginosa to predation pressure. P. aeruginosa persisted when coincubated with the bacterivorous Acanthamoeba castellanii for extended periods and produced genetic and phenotypic variants. Sequencing of late-stage amoeba-adapted P. aeruginosa isolates demonstrated single nucleotide polymorphisms within genes that encode known virulence factors, and this correlated with a reduction in expression of virulence traits. Virulence for the nematode Caenorhabditis elegans was attenuated in late-stage amoeba-adapted P. aeruginosa compared to early-stage amoeba-adapted and nonadapted counterparts. Further, late-stage amoeba-adapted P. aeruginosa showed increased competitive fitness and enhanced survival in amoebae as well as in macrophage and neutrophils. Interestingly, our findings indicate that the selection imposed by amoebae resulted in P. aeruginosa isolates with reduced virulence and enhanced fitness, similar to those recovered from chronic cystic fibrosis infections. Thus, predation by protozoa and long-term colonization of the human host may represent similar environments that select for similar losses of gene function. IMPORTANCE Pseudomonas aeruginosa is an opportunistic pathogen that causes both acute infections in plants and animals, including humans, and chronic infections in immunocompromised and cystic fibrosis patients. This bacterium is commonly found in soils and water, where bacteria are constantly under threat of being consumed by bacterial predators, e.g., protozoa. To escape being killed, bacteria have evolved a suite of mechanisms that protect them from being consumed or digested. Here, we examined the effect of long-term predation on the genotypes and phenotypes expressed by P. aeruginosa. We show that long-term coincubation with protozoa gave rise to mutations that resulted in P. aeruginosa becoming less pathogenic. This is particularly interesting as similar mutations arise in bacteria associated with chronic infections. Importantly, the genetic and phenotypic traits possessed by late-stage amoeba-adapted P. aeruginosa are similar to those observed in isolates obtained from chronic cystic fibrosis infections. This notable overlap in adaptation to different host types suggests similar selection pressures among host cell types as well as similar adaptation strategies.