Toxin complex (Tc) toxins are virulence factors of pathogenic bacteria. Tcs are composed of three subunits: TcA, TcB and TcC. TcA facilitates receptor-toxin interaction and membrane permeation, TcB and TcC form a toxin-encapsulating cocoon. While the mechanisms of holotoxin assembly and pore formation have been described, little is known about receptor binding of TcAs. Here, we identify heparins/heparan sulfates and Lewis antigens as receptors for different TcAs from insect and human pathogens. Glycan array screening reveals that all tested TcAs bind negatively charged heparins. Cryo-EM structures of Morganella morganii TcdA4 and Xenorhabdus nematophila XptA1 reveal that heparins/heparan sulfates unexpectedly bind to different regions of the shell domain, including receptor-binding domains. In addition, Photorhabdus luminescens TcdA1 binds to Lewis antigens with micromolar affinity. Here, the glycan interacts with the receptor-binding domain D of the toxin. Our results suggest a glycan dependent association mechanism of Tc toxins on the host cell surface.