Porphyromonas gingivalis, a gram-negative bacterium, has been linked to the onset and progression of periodontitis, a chronic inflammatory disease of the supporting tissues of the teeth. A major virulence factor of P. gingivalis is an extracellular complex of Arg- and Lys-specific proteinases and adhesins designated the RgpA-Kgp complex (formerly the PrtR-PrtK complex). In this study we show that the RgpA-Kgp complex, when used as an immunogen with incomplete Freund adjuvant (IFA), protects against challenge with invasive and noninvasive strains of P. gingivalis in the murine lesion model. We identified a variety of peptide vaccine candidates from the RgpA and Kgp polyprotein sequences that involved the putative active site histidine of both proteinases and five repeat motifs in the adhesin domains of both polyproteins implicated in aggregation and binding to host substrates, designated adhesin-binding motif (ABM) peptides. These peptides were synthesized using standard, solid-phase protocols for 9-fluorenylmethoxy carbonyl chemistry with S-acetylmercaptoacetic acid (SAMA) as the N-terminal residue. The SAMA-peptides were then conjugated to diphtheria toxoid and used with IFA to immunize BALB/c mice. Both active-site peptides and three of the five ABM peptides gave protection (P < 0.005) against challenge with P. gingivalis in the murine lesion model. The three ABM peptide sequences that conferred protection exist within a 100-residue span in the RgpA44 and Kgp39 adhesins of the RgpA-Kgp complex. Protective anti-RgpA-Kgp complex mouse antisera recognized the RgpA27, Kgp39, and RgpA44 adhesins in an immunoblot. Epitope mapping of the RgpA27 adhesin using the protective anti-RgpA-Kgp antisera identified a major protective epitope that mapped immediately N terminal to one of the protective ABM peptides in the 100-residue span in RgpA44 and Kgp39. This identified protective epitope contains clusters of basic residues spatially surrounded by hydrophobic amino acids, a finding which is characteristic of a heparin binding motif.