Helicobacter pylori adhesion to gastric epithelial cells constitutes a key step in the establishment of a successful infection of the gastric mucosa. The high representation of outer membrane proteins in the bacterial genome suggests the relevance of those proteins in the establishment of profitable interactions with the host gastric cells. Gastric epithelial cells are protected by a mucous layer gel, mainly consisting of the MUC5AC and MUC6 mucins. In addition to this protective role, mucins harbor glycan-rich domains that constitute preferential binding sites of many pathogens. In this article we review the main players in the process of H. pylori adhesion to gastric epithelial cells, which contribute decisively to the high prevalence and chronicity of H. pylori infection. The BabA adhesin recognizes both H-type 1 and Lewis b blood-group antigens expressed on normal gastric mucosa of secretor individuals, contributing to the initial steps of infection. Upon colonization, persistent infection induces an inflammatory response with concomitant expression of sialylated antigens. The SabA adhesin mediates H. pylori binding to inflamed gastric mucosa by recognizing sialyl-Lewis a and sialyl-Lewis x antigens. The expression of the BabA and SabA adhesins is tightly regulated, permitting the bacteria to rapidly adapt to the changes of glycosylation of the host gastric mucosa that occur during infection, as well as to escape from the inflammatory response. The growing knowledge of the interactions between the bacterial adhesins and the host receptors will contribute to the design of alternative strategies for eradication of the infection.