Porphyromonas gingivalis contains many virulence factors that have been implicated as participants in the progression of periodontal disease. It has been shown to produce proteinases of "trypsin-like" specificity in a number of molecular forms, but previous work in our laboratory resulted in the purification of a major arginine-specific cysteine proteinase, gingipain, which contradicted this supposed specificity. In this study, separate proteinases with arginine and lysine specificity were isolated from a high molecular mass fraction of the P. gingivalis culture fluid. The arginine-specific enzyme was found, by amino acid sequencing studies, to be a high molecular mass form of gingipain, formed by the 50-kDa gingipain noncovalently complexed with 44-kDa binding proteins, subsequently identified as hemagglutinins. The 60-kDa lysine-specific proteinase, referred to as Lys-gingipain, was also found to have one of these hemagglutinins complexed with it in the same manner. Lys-gingipain was found to be a cysteine proteinase with optimal activity and stability at pH 8.0-8.5 and was extensively characterized in terms of its specificity and activation characteristics. The proteinase-hemagglutinin complexes may be important in the uptake of hemin, a vital metabolite for P. gingivalis, via hemagglutination and subsequent hemolysis of erythrocytes.