A dual-receptor interaction with a polysialoganglioside and synaptic vesicle glycoprotein 2 (SV2) is required for botulinum neurotoxin A (BoNT) toxicity. Here, we review what is currently known about the BoNT/A-SV2 interaction based on structural studies. Currently, five crystal structures of the receptor-binding domain (Hc) of BoNT subtypes A1 and A2 complexed to the large luminal domain (LD4) of SV2C have been determined. On the basis of the available structures, we will discuss the importance of protein-protein and protein-carbohydrate interactions for BoNT/A toxicity as well as the high plasticity of BoNT/A for receptor recognition by tolerating a variety of side-chain interactions at the interface. A plausible explanation how receptor-binding specificity of BoNT/A may be achieved without an extensive and conserved side chain-side chain interaction network will be provided.