The adherence of the human gastric pathogen Helicobacter pylori to the gastric mucosa is widely assumed to play a substantial role in initial colonization and long-term persistence in the human stomach. In the past, a couple of putative adhesins were identified, most of which were members of the large outer membrane protein (OMP) family of H. pylori. Among these, the BabA protein was shown to recognize the Leb antigen, which is presented as a dominant surface structure in the gastric mucosa. The SabA adhesin binds to sialylated antigens, which are up-regulated in inflamed gastric tissue. Other OMPs, such as AlpAB or HopZ were also shown to be involved in binding to gastric epithelial cells, but the corresponding receptors are unknown. The aim of this review is to summarize recent data giving new insights in binding specificities of H. pylori adhesins and their role in pathogenesis and adaptation to the host.