With the availability of complete DNA sequences for many prokaryotic and eukaryotic genomes, and soon for the human genome itself, it is important to develop reliable proteome-wide approaches for a better understanding of protein function. As elementary constituents of cellular protein complexes and pathways, protein-protein interactions are key determinants of protein function. Here we have built a large-scale protein-protein interaction map of the human gastric pathogen Helicobacter pylori. We have used a high-throughput strategy of the yeast two-hybrid assay to screen 261 H. pylori proteins against a highly complex library of genome-encoded polypeptides. Over 1,200 interactions were identified between H. pylori proteins, connecting 46.6% of the proteome. The determination of a reliability score for every single protein-protein interaction and the identification of the actual interacting domains permitted the assignment of unannotated proteins to biological pathways.