The botulinum neurotoxins are potent molecules that are not only responsible for the lethal paralytic disease botulism, but have also been harnessed for therapeutic uses in the treatment of an increasing number of chronic neurological and neuromuscular disorders, in addition to cosmetic applications. The toxins act at the cholinergic nerve terminals thanks to an efficient and specific mechanism of cell recognition which is based on a dual receptor system that involves gangliosides and protein receptors. Binding to surface-anchored gangliosides is the first essential step in this process. Here, we determined the X-ray crystal structure of the binding domain of BoNT/E, a toxin of clinical interest, in complex with its GD1a oligosaccharide receptor. Beyond confirmation of the conserved ganglioside binding site, we identified key interacting residues that are unique to BoNT/E and a significant rearrangement of loop 1228–1237 upon carbohydrate binding. These observations were also supported by thermodynamic measurements of the binding reaction and assessment of ganglioside selectivity by immobilised-receptor binding assays. These results provide a structural basis to understand the specificity of BoNT/E for complex gangliosides.