The primary productivity of coral–dinoflagellate symbiosis is classically viewed as nitrogen (N)-limited. However, the recent discovery of N-fixing bacteria residing within coral tissues challenges this view. This study investigated the diversity and abundance of N-fixing bacteria associated with Hawaiian corals of the genus Montipora. Phylogenetic analysis of a partial sequence of the nitrogenase gene (nifH), revealed a diverse group of N-fixing bacteria in association with Montipora capitata and Montipora flabellata. These nifH sequences were closely affiliated with known taxa in α-, β-, γ-, and δ-proteobacteria, as well as cyanobacteria. Gamma-proteobacteria were the dominant bacterial class represented, and bacteria closely related to the genus Vibrio were the prevailing group within this class. Quantitative PCR was used to evaluate the abundance of the dominant class of N-fixing bacteria from different parts of four M. capitata colonies. The abundance of the dominant γ-proteobacteria was positively correlated (p = 0.001) with the abundance of symbiotic dinoflagellates, suggesting a physiological relationship between the two coral symbionts. The evidence obtained in this study suggests that N-limitation may not be a major regulator of the productivity of dinoflagellate symbionts of corals, but provides impetus for renewed investigation into N-cycling in this multi-partner symbiosis.