The Gram-negative pathogen Pseudomonas aeruginosa causes severe infections mainly in immunocompromised or cystic fibrosis patients and is able to resist antimicrobial treatments. The extracellular lectin LecB plays a key role in bacterial adhesion to the host and biofilm formation. For the inhibition of LecB, we designed and synthesized a set of fucosyl amides, sulfonamides, and thiourea derivatives. Then, we analyzed their binding to LecB in competitive and direct binding assays. We identified β-fucosyl amides as unprecedented high-affinity ligands in the two-digit nanomolar range. X-ray crystallography of one α- and one β-anomer of N-fucosyl amides in complex with LecB revealed the interactions responsible for the high affinity of the β-anomer at atomic level. Further, the molecules showed good stability in murine and human blood plasma and hepatic metabolism, providing a basis for future development into antibacterial drugs.