Helicobacter pylori from different individuals exhibits substantial genetic diversity. However, the kinetics of bacterial diversification after infection with a single strain is poorly understood. We investigated evolution of H. pylori following long-term infection in the primate stomach; Rhesus macaques were infected with H. pylori strain USU101 and then followed for 10 years. H. pylori was regularly cultured from biopsies, and single colony isolates were analyzed. At 1-year, DNA fingerprinting showed that all output isolates were identical to the input strain; however, at 5-years, different H. pylori fingerprints were observed. Microarray-based comparative genomic hybridization revealed that long term persistence of USU101 in the macaque stomach was associated with specific whole gene changes. Further detailed investigation showed that levels of the BabA protein were dramatically reduced within weeks of infection. The molecular mechanisms behind this reduction were shown to include phase variation and gene loss via intragenomic rearrangement, suggesting strong selective pressure against BabA expression in the macaque model. Notably, although there is apparently strong selective pressure against babA, babA is required for establishment of infection in this model as a strain in which babA was deleted was unable to colonize experimentally infected macaques.