Contact-dependent inhibition (CDI) is a mechanism of interbacterial competition in Gram-negative bacteria. The critical component of CDI systems is a large protein named CdiA; it forms a filament on the bacterial cell surface and contains a toxin domain at its C-terminal end. Upon binding to a receptor protein on the surface of a neighboring cell, CdiA delivers the toxin domain through the outer membrane of the neighboring bacterium. The mechanism of that delivery process is poorly understood. We have characterized how CdiA from E. coli EC93 binds to its receptor, BamA, to understand how this binding event might initiate the process of toxin delivery. BamA is an essential protein that assembles β-barrel proteins into the outer membranes of all Gram-negative bacteria; this assembly process depends on BamA's unique ability to open laterally in the lipid bilayer through a gate in its own membrane-embedded β-barrel. Through site-specific photo-cross-linking and mutational analysis, we demonstrate that the BamA-CdiA interaction depends on a small number of non-conserved amino acids on the extracellular surface of BamA, but the protein interface extends over a region near BamA's lateral gate. We further demonstrate that BamA's lateral gate can open without disrupting the interaction with CdiA. CdiA thus appears to initially engage BamA in a manner that could allow it to utilize BamA's lateral gate in subsequent steps in the toxin translocation process.