Myxobacteria are famous for their ability to produce most intriguing secondary metabolites. Till recently, only terrestrial myxobacteria were in the focus of research. In this review, however, we discuss marine-derived myxobacteria, which are particularly interesting due to their relatively recent discovery and due to the fact that their very existence was called into question. The to-date-explored members of these halophilic or halotolerant myxobacteria are all grouped into the suborder Nannocystineae. Few of them were chemically investigated revealing around 11 structural types belonging to the polyketide, non-ribosomal peptide, hybrids thereof or terpenoid class of secondary metabolites. A most unusual structural type is represented by salimabromide from Enhygromyxa salina. In silico analyses were carried out on the available genome sequences of four bacterial members of the Nannocystineae, revealing the biosynthetic potential of these bacteria.