Helicobacter pylori is an important human pathogen and a common cause of peptic ulcers and gastric cancer. Despite H. pylori provoking strong innate and adaptive immune responses, the bacterium is able to successfully establish long-term infections. Vitronectin (Vn), a component of both the extracellular matrix and plasma, is involved in many physiological processes, including regulation of the complement system. The aim of this study was to define a receptor in H. pylori that binds Vn and determine the significance of the interaction for virulence. Surprisingly, by using proteomics, we found that the hydrogen peroxide-neutralizing enzyme catalase KatA is a major Vn-binding protein. Deletion of the katA gene in three different strains resulted in impaired binding of Vn. Recombinant KatA was generated and shown to bind with high affinity to a region between heparin-binding domain 2 and 3 of Vn that differs from previously characterised bacterial binding sites on the molecule. In terms of function, KatA protected H. pylori from complement-mediated killing in a Vn-dependent manner. Taken together, the virulence factor KatA is a Vn-binding protein that moonlights on the surface of H. pylori to promote bacterial evasion of host innate immunity.