The discovery of quorum sensing (QS) communication systems regulating bacterial virulence has afforded a novel opportunity for controlling infectious bacteria by interfering with QS. Pseudomonas aeruginosa is an example of an opportunistic human pathogen for which N-acyl homoserine lactone (AHL)-related compounds have been described as potent inhibitors of biofilm formation and virulence factors, given their similarity to the natural QS autoinducers (AHLs). Our purpose was to design potent analogs of N-butanoyl-L-homoserine lactone (C4-HSL) and to screen them for biological activity. Eleven original compounds characterized by the modification of the lactone moiety were screened for their ability to impair biofilm formation. Among them, compound 11 was able to modify the growth kinetics and to restrict the number of adherent cells when added from the early stages of biofilm formation (i.e., adhesion and microcolony formation) in a dose-dependent manner. To demonstrate antagonism with C4-HSL, we showed that the inhibition of biofilm formation by compound 11 was impaired when C4-HSL was added. Structure-activity relationships are discussed with respect to the results obtained.