Helicobacter pylori infects half of the world's population and strains that encode the cag type IV secretion system for injection of the oncoprotein CagA into host gastric epithelial cells are associated with elevated levels of cancer. CagA translocation into host cells is dependent on interactions between the H. pylori adhesin protein HopQ and human CEACAMs. Here, we present high-resolution structures of numerous HopQ-CEACAM complexes and CEACAMs in their monomeric and dimeric forms establishing that HopQ uses a coupled folding and binding mechanism to engage the canonical CEACAM dimerization interface for CEACAM recognition. By combining mutagenesis with biophysical and functional analyses, we show that the modes of CEACAM recognition by HopQ and CEACAMs themselves are starkly different. Our data describe precise molecular mechanisms by which microbes exploit host CEACAMs for infection and enable future development of novel oncoprotein translocation inhibitors and H. pylori-specific antimicrobial agents.