The fucose-specific lectin LecB is implicated in tissue binding and biofilm formation by the opportunistic pathogen Pseudomonas aeruginosa, which causes severe respiratory tract infections mainly in immunocompromised patients or cancer patients undergoing chemotherapy. With a view to developing multivalent LecB inhibitors as novel antibacterial agents, a combinatorial library containing 15 625 tetravalent C-fucosyl peptide dendrimers with the basic structure (CFuc-X(6)X(5)X(4))(4)(LysX(3)X(2)X(1))(2)LysIleHisNH(2) (CFuc=alpha-L-fucosyl acetic acid, X(1-6)=amino acids, Lys=lysine branching) was screened for lectin binding using on-bead binding assays. Ten tetravalent and three octavalent dendrimers derived from the identified sequences were prepared by solid-phase peptide synthesis (SPPS), cleaved from the resin, and purified by preparative HPLC. Relative affinities of these soluble ligands to LecB were determined by an enzyme-linked lectin assay (ELLA). Strong binding was observed for tetravalent and octavalent ligands, with up to 440-fold enhancement in potency over fucose for the octavalent cationic dendrimer 2G3 (CFuc-LysPro)(8)(LysLeuPhe)(4)(LysLysIle)(2)LysHisIleNH(2)). Mono- and divalent controls showed affinities similar to fucose, highlighting the importance of multivalency for binding. Docking studies showed that the C-fucosyl group of the dendrimers can adopt the same binding mode as fucose itself, with the peptide arms protruding from the binding pocket and establishing specific contacts with the lectin.