Staphylococcus aureus is a serious human pathogen that employs a number of virulence factors as part of its pathogenesis. The purpose of the present study was to explore marine bacteria as a source of compounds that modulate virulence gene expression in S. aureus. During the global marine Galathea 3 expedition, a strain collection was established comprising bacteria that express antimicrobial activity against Vibrio anguillarum and/or Staphylococcus aureus. Within this collection we searched colony material, culture supernatants, and cell extracts for virulence modulating activity showing that 68 out of 83 marine bacteria (affiliated with the Vibrionaceae and Pseudoalteromonas sp.) influenced expression of S. aureus hla encoding α-hemolysin toxin and/or spa encoding Protein A. The isolate that upon initial screening showed the highest degree of interference (crude ethyl acetate extract) was a Vibrio nigripulchritudo. Extraction, purification and structural elucidation revealed a novel siderophore, designated nigribactin, which induces spa transcription. The effect of nigribactin on spa expression is likely to be independent from its siderophore activity, as another potent siderophore, enterobactin, failed to influence S. aureus virulence gene expression. This study shows that marine microorganisms produce compounds with potential use in therapeutic strategies targeting virulence rather than viability of human pathogens.