► Clostridium botulinum neurotoxin forms a progenitor complex with hemagglutinins. ► X-ray structures of the hemagglutinin/oligosaccharides complexes were determined. ► α2–3-Sialylated oligosaccharide bound to hemagglutinin tightly. ► α2–6-Sialylated oligosaccharide bound to hemagglutinin with a low occupancy. ► A binding assay also showed a higher affinity for α2–3-sialylated oligosaccharide. Clostridium botulinum produces the botulinum neurotoxin, forming a large complex as progenitor toxins in association with non-toxic non-hemagglutinin and/or several different hemagglutinin (HA) subcomponents, HA33, HA17 and HA70, which bind to carbohydrate of glycoproteins from epithelial cells in the infection process. To elucidate the carbohydrate recognition mechanism of HA70, X-ray structures of HA70 from type C toxin (HA70/C) in complexes with sialylated oligosaccharides were determined, and a binding assay by the glycoconjugate microarray was performed. These results suggested that HA70/C can recognize both α2–3- and α2–6-sialylated oligosaccharides, and that it has a higher affinity for α2–3-sialylated oligosaccharides.