Infections with the Gram-negative bacterium Pseudomonas aeruginosa result in a high mortality among immunocompromised patients and those with cystic fibrosis. The pathogen can switch from planktonic life to biofilms, and thereby shields itself against antibiotic treatment and host immune defense to establish chronic infections. The bacterial protein LecA, a C-type lectin, is a virulence factor and an integral component for biofilm formation. Inhibition of LecA with its carbohydrate ligands results in reduced biofilm mass, a potential Achilles heel for treatment. Here, we report the development and optimization of a fluorescence polarization-based competitive binding assay with LecA for application in screening of potential inhibitors. As a consequence of the low affinity of d-galactose for LecA, the fluorescent ligand was optimized to reduce protein consumption in the assay. The assay was validated using a set of known inhibitors of LecA and IC50 values in good agreement with the known Kd values were obtained. Finally, we employed the optimized assay to screen sets of synthetic thio-galactosides and natural blood group antigens and report their structure-activity relationship. In addition, we evaluated a multivalent fluorescent assay probe for LecA and report its applicability in an inhibition assay.