Microorganisms embedded in a biofilm are significantly more resistant to antimicrobial agents and the defences of the human immune system, than their planktonic counterpart. Consequently, compounds that can inhibit biofilm formation are of great interest for novel therapeutics. In this study, a screening approach was used to identify novel cyclic dipeptides that have anti-biofilm activity against oral pathogens. Five new active compounds were identified that prevent biofilm formation by the cariogenic bacterium Streptococcus mutans and the pathogenic fungus Candida albicans. These compounds also inhibit the adherence of microorganisms to a hydroxylapatite surface. Further investigations were conducted on these compounds to establish the structure-activity relationship, and it was deduced that the common cleft pattern is required for these molecules to act effectively against biofilms.