Myxobacteria are common in terrestrial habitats and well known for their formation of fruiting bodies and production of secondary metabolites. We studied a cluster of myxobacteria consisting only of sequences of marine origin (marine myxobacteria cluster, MMC) in sediments of the North Sea. Using a specific PCR, MMC sequences were detected in North Sea sediments down to 2.2 m depth, but not in the limnetic section of the Weser estuary and other freshwater habitats. In the water column, this cluster was only detected on aggregates up to a few meters above the sediment surface, but never in the fraction of free-living bacteria. A quantitative real-time PCR approach revealed that the MMC constituted up to 13% of total bacterial 16S rRNA genes in surface sediments of the North Sea. In a global survey, including sediments from the Mediterranean Sea, the Atlantic, Pacific and Indian Ocean and various climatic regions, the MMC was detected in most samples and to a water depth of 4300 m. Two fosmids of a library from sediment of the southern North Sea containing 16S rRNA genes affiliated with the MMC were sequenced. Both fosmids have a single unlinked 16S rRNA gene and no complete rRNA operon as found in most bacteria. No synteny to other myxobacterial genomes was found. The highest numbers of orthologues for both fosmids were assigned to Sorangium cellulosum and Haliangium ochraceum. Our results show that the MMC is an important and widely distributed but largely unknown component of marine sediment-associated bacterial communities.