Persistent infection with the gastric bacterial pathogen Helicobacter pylori causes gastritis and predisposes carriers to a high gastric cancer risk, but has also been linked to protection from allergic, chronic inflammatory and autoimmune diseases. In the course of tens of thousands of years of co-existence with its human host, H. pylori has evolved elaborate adaptations that allow it to persist in the hostile environment of the stomach in the face of a vigorous innate and adaptive immune response. For this review, we have identified several key immune cell types and signaling pathways that appear to be preferentially targeted by the bacteria to establish and maintain persistent infection. We explore the mechanisms that allow the bacteria to avoid detection by innate immune cells via their pattern recognition receptors, to escape T-cell mediated adaptive immunity, and to reprogram the immune system towards tolerance rather than immunity. The implications of the immunomodulatory properties of the bacteria for the prevention of allergic and auto-immune diseases in chronically infected individuals are also discussed.