Botulinum neurotoxins (BoNTs) are produced as progenitor toxin complexes (PTCs) by Clostridium botulinum. The PTCs are composed of BoNT and non-toxic neurotoxin-associated proteins (NAPs), which serve to protect and deliver BoNT through the gastrointestinal tract in food borne botulism. HA33 is a key NAP component that specifically recognizes host carbohydrates and helps enrich PTC on the intestinal lumen preceding its transport across the epithelial barriers. Here, we report the crystal structure of HA33 of type B PTC (HA33/B) in complex with lactose at 1.46Å resolution. The structural comparisons among HA33 of serotypes A-D reveal two different HA33-glycan interaction modes. The glycan-binding pockets on HA33/A and B are more suitable to recognize galactose-containing glycans in comparison to the equivalent sites on HA33/C and D. On the contrary, HA33/C and D could potentially recognize Neu5Ac as an independent receptor, whereas HA33/A and B do not. These findings indicate that the different oral toxicity and host susceptibility observed among different BoNT serotypes could be partly determined by the serotype-specific interaction between HA33 and host carbohydrate receptors. Furthermore, we have identified a key structural water molecule that mediates the HA33/B-lactose interactions. It provides the structural basis for development of new receptor-mimicking compounds, which have enhanced binding affinity with HA33 through their water-displacing moiety.