Botulinum neurotoxins (BoNTs) are highly poisonous substances that are also effective medicines. Accidental BoNT poisoning often occurs through ingestion of Clostridium botulinum-contaminated food. Here, we present the crystal structure of a BoNT in complex with a clostridial nontoxic nonhemagglutinin (NTNHA) protein at 2.7 angstroms. Biochemical and functional studies show that NTNHA provides large and multivalent binding interfaces to protect BoNT from gastrointestinal degradation. Moreover, the structure highlights key residues in BoNT that regulate complex assembly in a pH-dependent manner. Collectively, our findings define the molecular mechanisms by which NTNHA shields BoNT in the hostile gastrointestinal environment and releases it upon entry into the circulation. These results will assist in the design of small molecules for inhibiting oral BoNT intoxication and of delivery vehicles for oral administration of biologics.