Botulinum neurotoxins (BoNTs) are potent bacterial toxins. The high oral toxicity of BoNTs is largely attributed to the progenitor toxin complex (PTC), which is assembled from BoNT and nontoxic neurotoxin-associated proteins (NAPs) that are produced together with BoNT in bacteria. Here, we performed ex vivo studies to examine binding of the highly homogeneous recombinant NAPs to mouse small intestine. We also carried out the first comprehensive glycan array screening with the hemagglutinin (HA) component of NAPs. Our data confirmed that intestinal binding of the PTC is partly mediated by the HA moiety through multivalent interactions between HA and host carbohydrates. The specific HA-carbohydrate recognition could be inhibited by receptor-mimicking saccharides.