Clostridium botulinum strains produce a large-sized toxin complex (TC) that is composed of botulinum neurotoxin (BoNT), non-toxic non-hemagglutinin and three different hemagglutinins (HA-70, HA-33 and HA-17). HA components enhance toxin delivery across the intestinal cell wall in a sugar chain-dependent manner. Here we characterized the sugar recognition of serotype D strain 1873 (D-1873) botulinum L-TC. Most L-TCs produced by serotype C and D strains bind to cells via interactions between HA-33 and cell surface sialo-oligosaccharides. However, like the previously reported L-TC produced by serotype C strain Yoichi (C-Yoichi), D-1873 L-TC binds only to cells that have been treated with neuraminidase, indicating that they recognize asialo-oligosaccharides. The D-1873 HA-33 amino acid sequence is similar to that of C-Yoichi, but had lower similarity to the majority of serotype C and D HA-33s. A comparison of TC component primary structures for 12 serotype C and D strains suggested that at least three types of HA-33 genes exist, and these are shuffled among the serotype C and D strains independently of BoNT serotype. This shuffling produces the distinct sugar recognition of serotype C and D botulinum TCs.