Helicobacter pylori binds a number of host cell proteins, including the plasma protein plasminogen, which is the proenzyme of the serine protease plasmin. Two H. pylori plasminogen-binding proteins have been described; however, no genes were identified. Here we report the use of a phage display library to clone two genes from the H. pylori CCUG 17874 genome that mediate binding to plasminogen. DNA sequence analysis of one of these genes revealed 96.6% homology with H. pylori 26695 HP0508. A subsequent database search revealed that the amino acid sequence of a lysine-rich C-terminal segment of HP0508 is identical to the C terminus of HP0863. Recombinant proteins expressed from HP0508 and HP0863 bound plasminogen specifically and in a lysine-dependent manner. We designate these genes pgbA and pgbB, respectively. These proteins are expressed by a variety of H. pylori strains, have surface-exposed domains, and do not inhibit plasminogen activation. These results indicate that pgbA and pgbB may allow H. pylori to coat its exterior with plasminogen, which subsequently can be activated to plasmin. The surface acquisition of protease activity may enhance the virulence of H. pylori.