A wide range of prescreening tests for antimicrobial activity of 59 bacterial isolates from sediments of Ria Formosa Lagoon (Algarve, Portugal) disclosed Vibrio spartinae 3.6 as the most active antibacterial producing strain. This bacterial strain, which has not previously been submitted for chemical profiling, was subjected to de novo whole genome sequencing, which aided in the discovery and elucidation of a prodigiosin biosynthetic gene cluster that was predicted by the bioinformatic tool KEGG BlastKoala. Comparative genomics led to the identification of a new membrane di-iron oxygenase-like enzyme, annotated as Vspart_02107, which is likely to be involved in the biosynthesis of cycloprodigiosin and analogues. The combined genomics-metabolomics profiling of the strain led to the isolation and identification of one new branched-chain prodigiosin (5) and to the detection of two new cyclic forms. Furthermore, the evaluation of the minimum inhibitory concentrations disclosed the major prodigiosin as very effective against multi-drug-resistant pathogens including Stenotrophomonas maltophilia, a clinical isolate of Listeria monocytogenes, as well as some human pathogens reported by the World Health Organization as prioritized targets.