Taxonomic characterization was performed on the putative N(2)-fixing microbiota associated with the coral species Mussismilia hispida, and with its sympatric species Palythoa caribaeorum, P. variabilis, and Zoanthus solanderi, off the coast of São Sebastião (São Paulo State, Brazil). The 95 isolates belonged to the Gammaproteobacteria according to the 16S rDNA gene sequences. In order to identify the isolates unambiguously, pyrH gene sequencing was carried out. The majority of the isolates (n = 76) fell within the Vibrio core group, with the highest gene sequence similarity being towards Vibrio harveyi and Vibrio alginolyticus. Nineteen representative isolates belonging to V. harveyi (n = 7), V. alginolyticus (n = 8), V. campbellii (n = 3), and V. parahaemolyticus (n = 1) were capable of growing six successive times in nitrogen-free medium and some of them showed strong nitrogenase activity by means of the acetylene reduction assay (ARA). It was concluded that nitrogen fixation is a common phenotypic trait among Vibrio species of the core group. The fact that different Vibrio species can fix N(2) might explain why they are so abundant in the mucus of different coral species.