How botulinum neurotoxins (BoNTs) cross the host intestinal epithelial barrier in foodborne botulism is poorly understood. Here, we present the crystal structure of a clostridial hemagglutinin (HA) complex of serotype BoNT/A bound to the cell adhesion protein E-cadherin at 2.4 angstroms. The HA complex recognizes E-cadherin with high specificity involving extensive intermolecular interactions and also binds to carbohydrates on the cell surface. Binding of the HA complex sequesters E-cadherin in the monomeric state, compromising the E-cadherin-mediated intercellular barrier and facilitating paracellular absorption of BoNT/A. We reconstituted the complete 14-subunit BoNT/A complex using recombinantly produced components and demonstrated that abolishing either E-cadherin- or carbohydrate-binding of the HA complex drastically reduces oral toxicity of BoNT/A complex in vivo. Together, these studies establish the molecular mechanism of how HAs contribute to the oral toxicity of BoNT/A.