Advances in genomic microbial taxonomy have opened the way to create a more universal and transparent concept of species but is still in a transitional stage towards becoming a defining robust criteria for describing new microbial species with minimum features obtained using both genome and classical polyphasic taxonomies. Here we performed advanced microbial taxonomies combined with both genome-based and classical approaches for new agarolytic vibrio isolates to describe not only a novel Vibrio species but also a member of a new Vibrio clade. Two novel vibrio strains (Vibrio astriarenae sp. nov. C7T and C20) showing agarolytic, halophilic and fermentative metabolic activity were isolated from a seawater sample collected in a coral reef in Okinawa. Intraspecific similarities of the isolates were identical in both sequences on the 16S rRNA and pyrH genes, but the closest relatives on the molecular phylogenetic trees on the basis of 16S rRNA and pyrH gene sequences were V. hangzhouensis JCM 15146T (97.8% similarity) and V. agarivorans CECT 5085T (97.3% similarity), respectively. Further multilocus sequence analysis (MLSA) on the basis of 8 protein coding genes (ftsZ, gapA, gyrB, mreB, pyrH, recA, rpoA, and topA) obtained by the genome sequences clearly showed the V. astriarenae strain C7T and C20 formed a distinct new clade protruded next to V. agarivorans CECT 5085T. The singleton V. agarivorans has never been included in previous MLSA of Vibrionaceae due to the lack of some gene sequences. Now the gene sequences are completed and analysis of 100 taxa in total provided a clear picture describing the association of V. agarivorans into pre-existing concatenated network tree and concluded its relationship to our vibrio strains. Experimental DNA-DNA hybridization (DDH) data showed that the strains C7T and C20 were conspecific but were separated from all of the other Vibrio species related on the basis of both 16S rRNA and pyrH gene phylogenies (e.g., V. agarivorans CECT 5085T, V. hangzhouensis JCM 15146T V. maritimus LMG 25439T, and V. variabilis LMG 25438T). In silico DDH data also supported the genomic relationship. The strains C7T also had less than 95% average amino acid identity (AAI) and average nucleotide identity (ANI) towards V. maritimus C210, V. variabilis C206, and V. mediterranei AK1T, V. brasiliensis LMG 20546T, V. orientalis ATCC 33934T, and V. sinaloensis DSM 21326. The name Vibrio astriarenae sp. nov. is proposed with C7 as the type strains. Both V. agarivorans CECT 5058T and V. astriarenae C7T are members of the newest clade of Vibrionaceae named Agarivorans.