Variation of surface antigen expression is a mechanism used by microbes to adapt to and persist within their host habitats. Helicobacter pylori, a persistent bacterial colonizer of the human stomach, can alter its surface Lewis (Le) antigen expression. We examined H. pylori colonization in mice to test the hypothesis that host phenotype selects for H. pylori (Le) phenotypes. When wild-type and Leb-expressing transgenic FVB/N mice were challenged with H. pylori strain HP1, expressing Lex and Ley, we found that bacterial populations recovered after 8 mo from Le b-transgenic, but not wild-type, mice expressed Leb. Changes in Le phenotype were linked to variation of a putative galactosyltransferase gene (β-(1,3)galT); mutagenesis and complementation revealed its essential role in type I antigen expression. These studies indicate that H. pylori evolves to resemble the host's gastric Le phenotype, and reveal a bacterial genetic locus that is subject to host-driven selection pressure.