Fusobacterium nucleatum is overrepresented in the colon microbiome of colorectal cancer patients and has been associated with tumor growth enhancement and metastasis. A pivotal pathogenic factor, the autotransporter adhesin Fap2, facilitates association to cancer and immune cells via the receptors Gal-GalNAc and TIGIT, respectively, leading to deactivation of immune cells. Mechanistic details of the Fap2/TIGIT interaction remain elusive as no structural data are available. Here, we report a system to recombinantly express functional Fap2 on the Escherichia coli surface, which interacts with Gal-GalNAc on cancer cells and with purified TIGIT with submicromolar affinity. Cryo-EM structures of Fap2, alone and in complex with TIGIT, show that the elongated ~50 nm long Fap2 extracellular region binds to TIGIT on its membrane-distal tip via an extension of a β-helix domain. Moreover, by combining structure predictions, cryo-EM, docking and molecular dynamics simulations, we identified a binding pit for Gal-GalNAc on the tip of Fap2.