During a global research expedition, more than five hundred marine bacterial strains capable of inhibiting the growth of pathogenic bacteria were collected. The purpose of the present study was to determine if these marine bacteria are also a source of compounds that interfere with the agr quorum sensing system that controls virulence gene expression in Staphylococcus aureus. Using a gene reporter fusion bioassay, we recorded agr interference as enhanced expression of spa, encoding Protein A, concomitantly with reduced expression of hla, encoding α-hemolysin, and rnaIII encoding RNAIII, the effector molecule of agr. A marine Photobacterium produced compounds interfering with agr in S. aureus strain 8325-4, and bioassay-guided fractionation of crude extracts led to the isolation of two novel cyclodepsipeptides, designated solonamide A and B. Northern blot analysis confirmed the agr interfering activity of pure solonamides in both S. aureus strain 8325-4 and the highly virulent, community-acquired strain USA300 (CA-MRSA). To our knowledge, this is the first report of inhibitors of the agr system by a marine bacterium.