The fimbriae of Porphyromonas gingivalis mediate critical roles in host colonization and evasion of innate defenses and comprise polymerized fimbrilin (FimA) associated with quantitatively minor accessory proteins (FimCDE) of unknown function. We now show that P. gingivalis fimbriae lacking FimCDE fail to interact with the CXC-chemokine receptor 4 (CXCR4), and bacteria expressing FimCDE-deficient fimbriae cannot exploit CXCR4 in vivo for promoting their persistence, as the wild-type organism does. Consistent with these loss-of-function experiments, purified FimC and FimD (but not FimE) were shown to interact with CXCR4. However, significantly stronger binding was observed when a combination of all three proteins was allowed to interact with CXCR4. In addition, FimC and FimD bound to fibronectin and type 1 collagen, whereas FimE failed to interact with these matrix proteins. These data and the fact that FimE is required for the association of FimCDE with P. gingivalis fimbriae suggest that FimE may recruit FimC and FimD into a functional complex, rather than directly binding host proteins. Consistent with this notion, FimE was shown to bind both FimC and FimD. In summary, the FimCDE components cooperate and impart critical adhesive and virulence properties to P. gingivalis fimbriae.