Bacterial strains were isolated from sponge and green algae which were collected on the coast of Japan and Palau. The phylogenetic relationships of these isolates among marine species of the Cytophaga-Flavobacterium-Bacteroides complex were analysed by using their gyrB nucleotide sequences and translated peptide sequences (GyrB) in addition to 16S rDNA sequences. These isolates were closely related to the previously characterized marine Flexibacter species, [Flexibacter] maritimus and [Flexibacter] ovolyticus. These Flexibacter species are distantly related to Flexibacter flexilis, the type species of the genus Flexibacter, and phylogenetically belong to the family Flavobacteriaceae (according to analysis using both 16S rDNA and GyrB sequences). Their phylogenetic, chemotaxonomic and phenotypic characteristics prompted the proposal that these two species should be transferred to the new genus Tenacibaculum, as Tenacibaculum maritimum and Tenacibaculum ovolyticum, respectively. Two additional new species of the genus Tenacibaculum, Tenacibaculum mesophilum gen. nov., sp. nov. (= MBIC 1140T = IFO 16307T) and Tenacibaculum amylolyticum gen. nov., sp. nov. (= MBIC 4355T = IFO 16310T), which were isolated from sponges and macroalgae, are also reported. For taxonomic considerations at the species level, the resolution of gyrB sequences was superior to that of 16S rDNA sequences, and the grouping based on the gyrB phylogram was consistent with DNA-DNA hybridization results.