Botulinum neurotoxins (BoNTs) are the most toxic substances known and cause botulism in vertebrates. They have also emerged as effective and powerful reagents for cosmetic and medical applications. One important prerequisite for understanding BoNT function in disease, and the further development of the toxins for cosmetic and medical applications, is a detailed knowledge of BoNT interactions with non-toxic neurotoxin-associated proteins and cell surface receptors. Based on the substantial recent progress in obtaining high-resolution crystal structures of key BoNT complexes, we summarize the major advances in understanding BoNT interactions and discuss the resulting potential implications, in particular those relating to BoNT serotype A.