Adherence by Helicobacter pylori increases the risk of gastric disease. Here, we report that more than 95% of strains that bind fucosylated blood group antigen bind A, B, and O antigens (generalists), whereas 60% of adherent South American Amerindian strains bind blood group O antigens best (specialists). This specialization coincides with the unique predominance of blood group O in these Amerindians. Strains differed about 1500-fold in binding affinities, and diversifying selection was evident in babA sequences. We propose that cycles of selection for increased and decreased bacterial adherence contribute to babA diversity and that these cycles have led to gradual replacement of generalist binding by specialist binding in blood group O-dominant human populations.