The improper and uncontrolled uses of antibiotics againts pathogenic bacteria have resulted in the occurrence of Multi Drug Resistant (MDR) strains. There is now an urgency to find alternative antibiotics to combat the MDR strains especially Escherichia coli and Staphyllococcus aureus. Soft coral associated microorganisms are among the most interesting and promising marine natural product sources which produce polyketide and non ribosomal peptide products with various biological activities. In this study, marine bacteria were isolated from soft coral Lobophytum sp. collected from North Java Sea, and were screened for antibacterial activity against MDR strains. One out of 13 bacterial isolates were succesfully screened and were found to be active against both MDR strains, in which isolate LBTGA2 was active against resistant strains E. coli and against resistant S. aureus, respectively. The active isolate also amplified PKS (Polyketide Synthases) gene fragments necessary for the biosynthesis of polyketides. The molecular identification based on partial 16S DNA nukleotide sequences indicates that the active isolate was closely related to Paenibacillus campinasensis.