The cell density-dependent mechanism, quorum sensing (QS), regulates the expression of virulence factors. Its inhibition has been proposed as a promising new strategy to prevent bacterial pathogenicity. In this study, 827 strains from the microbiota of sea anemones and holothurians were screened for their ability to produce quorum-sensing inhibitor (QSI) compounds. The strain M3-10, identified as Vibrio alginolyticus by 16S rRNA gene sequencing, as well as ANIb and dDDH analyses, was selected for its high QSI activity. Bioassay-guided fractionation of the cell pellet extract from a fermentation broth of strain M3-10, followed by LC–MS and NMR analyses, revealed tyramine and N-acetyltyramine as the active compounds. The QS inhibitory activity of these molecules, which was confirmed using pure commercially available standards, was found to significantly inhibit Chromobacterium violaceum ATCC 12472 violacein production and virulence factors, such as pyoverdine production, as well as swarming and twitching motilities, produced by Pseudomonas aeruginosa PAO1. This constitutes the first study to screen QSI-producing strains in the microbiota of anemones and holothurians and provides an insight into the use of naturally produced QSI as a possible strategy to combat bacterial infections.