Burkholderia pseudomallei, the causative agent of melioidosis, contains a large pathogen genome (7.2 Mb) with ~2,000 genes of putative or unknown function. Interactions with potential hosts and environmental factors may induce rapid adaptations in these B. pseudomallei genes, which can be discerned through evolutionary analysis of multiple B. pseudomallei genomes. Here we show that several previously uncharacterized B. pseudomallei genes bearing genetic signatures of rapid adaptation (positive selection) can induce diverse cellular phenotypes when expressed in mammalian cells. Notably, several of these phenotypes are plausibly related to virulence, including multinuclear giant cell formation, apoptosis, and autophagy induction. Specifically, we show that BPSS0180, a type VI cluster-associated gene, is capable of inducing autophagy in both phagocytic and nonphagocytic mammalian cells. Following infection of macrophages, a B. pseudomallei mutant disrupted in BPSS0180 exhibited significantly decreased colocalization with LC3 and impaired intracellular survival; these phenotypes were rescued by introduction of an intact BPSS0180 gene. The results suggest that BPSS0180 may be a novel inducer of host cell autophagy that contributes to B. pseudomallei intracellular growth. More generally, our study highlights the utility of applying evolutionary principles to microbial genomes to identify novel virulence genes.