We describe a novel labeling strategy to site-specifically attach fluorophores, biotin, and proteins to the C terminus of the A1 subunit (CTA1) of cholera toxin (CTx) in an otherwise correctly assembled and active CTx complex. Using a biotinylated N-linked glycosylation reporter peptide attached to CTA1, we provide direct evidence that ∼12% of the internalized CTA1 pool reaches the ER. We also explored the sortase labeling method to attach the catalytic subunit of diphtheria toxin as a toxic warhead to CTA1, thus converting CTx into a cytolethal toxin. This new toxin conjugate enabled us to conduct a genetic screen in human cells, which identified ST3GAL5, SLC35A2, B3GALT4, UGCG, and ELF4 as genes essential for CTx intoxication. The first four encode proteins involved in the synthesis of gangliosides, which are known receptors for CTx. Identification and isolation of the ST3GAL5 and SLC35A2 mutant clonal cells uncover a previously unappreciated differential contribution of gangliosides to intoxication by CTx.