Ganglioside GM1 is the natural receptor for cholera toxin (CT) and heat-labile enterotoxin (LT), which are the causative agents of cholera and traveler's diarrhea, respectively. This observation suggests that small molecules interfering with this recognition process may prevent entry of the toxins into intestinal cells, thereby averting their devastating effects. Here, the terminal sugar of ganglioside GM1, galactose, was chosen as a lead in designing such receptor antagonists. Guided by the experimentally determined binding mode of galactose, we selected a "substructure" for searching the Available Chemicals Database, which led to the purchase of 35 galactose derivatives. Initial screening of these compounds in an LT ELISA revealed that 22 of them have a higher affinity for LT than galactose itself. A structurally diverse subset of these galactose derivatives was selected for determination of IC50 values in the LT ELISA and IC50 values in a CT assay, as well as for the determination of Kd's using the intrinsic fluorescence of LT. The best receptor antagonist found in this study was m-nitrophenyl alpha-galactoside with an IC50 of 0.6 (2) mM in the LT ELISA and 0.72 (4) mM in the CT assay, 100-fold lower than both IC50 values of galactose. Careful analysis of our binding data and comparison with crystal structures led to the derivation of correlations between the structure and affinity of the galactose derivatives. These characteristics will be used in the design of a second round of LT and CT receptor antagonists.