Most Helicobacter pylori strains express the BabA adhesin, which binds to ABO/Leb blood group antigens on gastric mucin and epithelial cells and is found more commonly in strains that cause peptic ulcers or gastric cancer, rather than asymptomatic infection. We and others have previously reported that in mice, gerbils, and rhesus macaques, expression of babA is lost, either by phase variation or by gene conversion, in which the babB paralog recombines into the babA locus. The functional significance of loss of babA expression is unknown. Here we report that in rhesus monkeys, there is independent selective pressure for loss of babA and for overexpression of BabB, which confers a fitness advantage. Surprisingly, loss of babA by phase variation or gene conversion is not dependent on the capacity of BabA protein to bind Leb, which suggests that it may have other, unrecognized functions. These findings have implications for the role of outer membrane protein diversity in persistent H. pylori infection.