Cysteine peptidases are key proteolytic virulence factors of the periodontopathogen Porphyromonas gingivalis, which causes chronic periodontitis, the most prevalent dysbiosis-driven disease in humans. Two peptidases, gingipain K (Kgp) and R (RgpA and RgpB), which differ in their selectivity after lysines and arginines, respectively, collectively account for 85% of the extracellular proteolytic activity of P. gingivalis at the site of infection. Therefore, they are promising targets for the design of specific inhibitors. Although the structure of the catalytic domain of RgpB is known, little is known about Kgp, which shares only 27% sequence identity. We report the high resolution crystal structure of a competent fragment of Kgp encompassing the catalytic cysteine peptidase domain and a downstream immunoglobulin superfamily-like domain, which is required for folding and secretion of Kgp in vivo. The structure, which strikingly resembles a tooth, was serendipitously trapped with a fragment of a covalent inhibitor targeting the catalytic cysteine. This provided accurate insight into the active site and suggested that catalysis may require a catalytic triad, Cys(477)-His(444)-Asp(388), rather than the cysteine-histidine dyad normally found in cysteine peptidases. In addition, a 20-Å-long solvent-filled interior channel traverses the molecule and links the bottom of the specificity pocket with the molecular surface opposite the active site cleft. This channel, absent in RgpB, may enhance the plasticity of the enzyme, which would explain the much lower activity in vitro toward comparable specific synthetic substrates. Overall, the present results report the architecture and molecular determinants of the working mechanism of Kgp, including interaction with its substrates.