Botulinum neurotoxins (BoNTs) and tetanus neurotoxin (TeNT) are the causative agents of the paralytic diseases botulism and tetanus, respectively. Entry of toxins into neurons is mediated through initial interactions with gangliosides, followed by binding to a protein co-receptor. Herein, we aimed to understand the mechanism through which individual neurotoxins recognize the carbohydrate motif of gangliosides. Using cell-based and in vitro binding assays, in conjunction with structure-driven site-directed mutagenesis, a conserved hydrophobic residue within the BoNTs that contributes to both affinity and specificity toward Sia5-containing gangliosides was identified. We demonstrate that targeted mutations within the Sia5 binding pocket result in the generation of neurotoxins that either bind and enter cells more efficiently (BoNT/A1 and BoNT/B) or display altered ganglioside binding specificity (TeNT). These data support a model in which recognition of Sia5 is largely driven by hydrophobic interactions between the sugar and the Sia5 binding site.