Botulinum neurotoxins (BoNTs) are potent bacterial toxins that cause paralysis at femtomolar concentrations by blocking neurotransmitter release. A 'double receptor' model has been proposed in which BoNTs recognize nerve terminals via interactions with both gangliosides and protein receptors that mediate their entry. Of seven BoNTs (subtypes A-G), the putative receptors for BoNT/A, BoNT/B and BoNT/G have been identified, but the molecular details that govern recognition remain undefined. Here we report the crystal structure of full-length BoNT/B in complex with the synaptotagmin II (Syt-II) recognition domain at 2.6 A resolution. The structure of the complex reveals that Syt-II forms a short helix that binds to a hydrophobic groove within the binding domain of BoNT/B. In addition, mutagenesis of amino acid residues within this interface on Syt-II affects binding of BoNT/B. Structural and sequence analysis reveals that this hydrophobic groove is conserved in the BoNT/G and BoNT/B subtypes, but varies in other clostridial neurotoxins. Furthermore, molecular docking studies using the ganglioside G(T1b) indicate that its binding site is more extensive than previously proposed and might form contacts with both BoNT/B and synaptotagmin. The results provide structural insights into how BoNTs recognize protein receptors and reveal a promising target for blocking toxin-receptor recognition.