Infections caused by Pseudomonas aeruginosa become increasingly difficult to treat because these bacteria have acquired various mechanisms for antibiotic resistance, which creates the need for mechanistically novel antibiotics. Such antibiotics might be developed by targeting enzymes involved in the iron uptake mechanism because iron is essential for bacterial survival. For P. aeruginosa, pyoverdine has been described as an important virulence factor that plays a key role in iron uptake. Therefore, inhibition of enzymes involved in the pyoverdine synthesis, such as PvdP tyrosinase, can open a new window for the treatment of P. aeruginosa infections. Previously, we reported phenylthiourea as the first allosteric inhibitor of PvdP tyrosinase with high micromolar potency. In this report, we explored structure-activity relationships (SAR) for PvdP tyrosinase inhibition by phenylthiourea derivatives. This enables identification of a phenylthiourea derivative (3c) with a potency in the submicromolar range (IC = 0.57 + 0.05 µM). Binding could be rationalized by molecular docking simulation and 3c was proved to inhibit the bacterial pyoverdine production and bacterial growth in P. aeruginosa PA01 cultures.