Botulinum neurotoxins have a very high affinity and specificity for their target cells requiring two different co-receptors located on the neuronal cell surface. Different toxin serotypes have different protein receptors; yet, most share a common ganglioside co-receptor, GT1b. We determined the crystal structure of the botulinum neurotoxin serotype A binding domain (residues 873–1297) alone and in complex with a GT1b analog at 1.7 Å and 1.6 Å, respectively. The ganglioside GT1b forms several key hydrogen bonds to conserved residues and binds in a shallow groove lined by Tryptophan 1266. GT1b binding does not induce any large structural changes in the toxin; therefore, it is unlikely that allosteric effects play a major role in the dual receptor recognition. Together with the previously published structures of botulinum neurotoxin serotype B in complex with its protein co-receptor, we can now generate a detailed model of botulinum neurotoxin's interaction with the neuronal cell surface. The two branches of the GT1b polysaccharide, together with the protein receptor site, impose strict geometric constraints on the mode of interaction with the membrane surface and strongly support a model where one end of the 100 Å long translocation domain helix bundle swing into contact with the membrane, initiating the membrane anchoring event.