Pseudomonas aeruginosa is one of world’s most threatening bacteria. In addition to the emerging prevalence of multi-drug resistant (MDR) strains, the bacterium also possesses a wide variety of virulence traits that worsen the course of the infections. Particularly, its ability to form biofilms that protect colonies from antimicrobial agents is a major cause of chronic and hard-to-treat infections in immune-compromised patients. This protective barrier also ensures cell growth on abiotic surfaces and thus enables bacterial survival on medical devices. Hence, as the WHO alerted to the need to develop new treatments, the use of anti-biofilm agents (ABAs) appeared as a promising approach. Given the selection pressure imposed by conventional antibiotics, a new therapeutic strategy has emerged that aims at reducing bacterial virulence without inhibiting cell growth. So-called anti-virulence agents (AVAs) would then restore the efficacy of conventional antibiotics (ATBs) or potentiate the effectiveness of the immune system. The last decade has seen the development of ABAs as AVAs against P. aeruginosa. This review aims to highlight the design strategy and critical features of these molecules to pave the way for further discoveries of highly potent compounds.