DsbA enzymes catalyze oxidative folding of proteins that are secreted into the periplasm of Gram-negative bacteria, and they are indispensable for the virulence of human pathogens such as Vibrio cholerae and Escherichia coli. Therefore, targeting DsbA represents an attractive approach to control bacterial virulence. X-ray crystal structures reveal that DsbA enzymes share a similar fold, however, the hydrophobic groove adjacent to the active site, which is implicated in substrate binding, is shorter and flatter in the structure of V. cholerae DsbA (VcDsbA) compared to E. coli DsbA (EcDsbA). The flat and largely featureless nature of this hydrophobic groove is challenging for the development of small molecule inhibitors. Using fragment-based screening approaches, we have identified a novel small molecule, based on the benzimidazole scaffold, that binds to the hydrophobic groove of oxidized VcDsbA with a KD of 446 ± 10 µM. The same benzimidazole compound has ~8-fold selectivity for VcDsbA over EcDsbA and binds to oxidized EcDsbA, with KD > 3.5 mM. We generated a model of the benzimidazole complex with VcDsbA using NMR data but were unable to determine the structure of the benzimidazole bound EcDsbA using either NMR or X-ray crystallography. Therefore, a structural basis for the observed selectivity is unclear. To better understand ligand binding to these two enzymes we crystallized each of them in complex with a known ligand, the bile salt sodium taurocholate. The crystal structures show that taurocholate adopts different binding poses in complex with VcDsbA and EcDsbA, and reveals the protein-ligand interactions that stabilize the different modes of binding. This work highlights the capacity of fragment-based drug discovery to identify inhibitors of challenging protein targets. In addition, it provides a starting point for development of more potent and specific VcDsbA inhibitors that act through a novel anti-virulence mechanism.