Adhesive interactions of cells are critical to tissue integrity. We show that infection with Porphyromonas gingivalis, a major pathogen in the periodontal disease periodontitis, interferes with both cell-matrix and cell-cell adhesion in the oral keratinocyte cell line HOK-16. Thus, infected cells showed reduced adhesion to extracellular matrix, changes in morphology from spread to rounded, and impaired motility on purified matrices in Transwell migration assays and scratch assays. Western blot analysis of P. gingivalis-challenged HOK-16 cells revealed proteolysis of focal contact components (e.g., focal adhesion kinase), adherens junction proteins (e.g., catenins), and adhesion signaling molecules (e.g., the tyrosine kinase SRC). Proteolysis was selective, since important components of adherens junctions (E-cadherin) or signaling molecules (extracellular signal-regulated kinases ERK1/2) were not degraded. The virulence factors gingipains, cysteine proteinases expressed by P. gingivalis, are likely responsible for this proteolytic attack, since they directly digested specific proteins in pull-down experiments, and their proteolytic activity was blocked by the cysteine proteinase inhibitor N-alpha-p-tosyl-L-lysine chloromethyl ketone and also by a caspase inhibitor. Proteolysis was strain dependent, such that ATCC 33277 and 381 had high proteolytic potential, whereas W50 showed almost no proteolytic activity. These findings may help explain the formation of gingival pockets between cementum and periodontal epithelium, a hallmark of periodontitis. Furthermore, they illustrate a new pathogenetic paradigm of infection whereby bacteria may disrupt the integrity of epithelia.