Two novel vibrio isolates (R-40492(T) and R-40493(T)) originating from the zoanthid Palythoa caribaeorum in Brazil in 2005 were taxonomically characterized by means of a polyphasic approach comprising multilocus sequence analysis (MLSA), DNA-DNA hybridization (DDH), ΔT(m) analysis and phenotypic characterization. Phylogenetic analysis based on 16S rRNA gene sequences showed that R-40492(T) and R-40493(T) fell within the genus Vibrio and were most closely related to each other with 99% similarity; similarities of these two novel isolates towards Vibrio neptunius LMG 20536(T), Vibrio coralliilyticus LMG 20984(T), Vibrio nigripulchritudo LMG 3896(T), Vibrio sinaloensis LMG 25238(T) and Vibrio brasiliensis LMG 20546(T) varied between 97.1 and 98.5%. DDH experiments showed that the two isolates had less than 15% relatedness to the phylogenetically most closely related Vibrio species. R-40492(T) and R-40493(T) had 55-57% relatedness to each other. The ΔT(m) between R-40492(T) and R-40493(T) was 6.12 °C. In addition, MLSA of concatenated sequences (16S rRNA, ftsZ, gyrB, recA, rpoA, topA, pyrH and mreB; 6035 bp in length) showed that the two novel isolates formed a separate branch with less than 92% concatenated gene sequence similarity towards known species of vibrios. Two novel species are proposed to accommodate these novel isolates, namely Vibrio variabilis sp. nov. (type strain, R-40492(T)=LMG 25438(T)=CAIM 1454(T)) and Vibrio maritimus sp. nov. (type strain, R-40493(T)=LMG 25439(T)=CAIM 1455(T)).