The natural compound zosteric acid, or p-(sulfoxy)cinnamic acid (ZA), is proposed as an alternative biocide-free agent suitable for preventive or integrative anti-biofilm approaches. Despite its potential, the lack of information concerning the structural and molecular mechanism of action involved in its anti-biofilm activity has limited efforts to generate more potent anti-biofilm strategies. In this study a 43-member library of small molecules based on ZA scaffold diversity was designed and screened against Escherichia coli to understand the structural requirements necessary for biofilm inhibition at sub-lethal concentrations. Considerations concerning the relationship between structure and anti-biofilm activity revealed that i) the para-sulfoxy ester group is not needed to exploit the anti-biofilm activity of the molecule, it is the cinnamic acid scaffold that is responsible for anti-biofilm performance; ii) the anti-biofilm activity of ZA derivatives depends on the presence of a carboxylate anion and, consequently, on its hydrogen-donating ability; iii) the conjugated aromatic system is instrumental to the anti-biofilm activities of ZA and its analogues. Using a protein pull-down approach, combined with mass spectrometry, the herein-defined active structure of ZA was matrix-immobilized, and was proved to interact with the E. coli NADH:quinone reductase, WrbA, suggesting a possible role of this protein in the biofilm formation process.