Laminated microbial mats thrive in nitrogen (N)-deplete shallow water ecosystems from the tropics to polar regions. Their broad geographic distribution is attributed to their ability to sequester combined N via N2 fixation. N2 fixation provides a biological mechanism for generating “new” N in these systems. Physiological, molecular, and culturing studies have revealed biochemically and taxonomically diverse microbial mat diazotrophic communities including a surprising preponderance of heterotrophic bacterial taxa. A combination of isolation, cultivation, and molecular characterization (amplification of a 362 bp segment of nifH and approximately 500 bp segment of 16S rRNA, followed by sequencing of the cloned amplification products) was used to determine the presence, diversity, and ubiquity of heterotrophic N2 fixers in cyanobacteria-dominated microbial mats obtained from Tomales Bay, CA, Sippewissett Salt Marsh, MA, and Bird Shoal, NC. The results demonstrate that several specific diazotrophic bacterial genera are found in microbial mats from widely disparate geographical locations and that heterotrophs play a larger role in mat N2 fixation dynamics than was previously thought. A large number of the isolates appear to be most closely related to the genus Vibrio. None of the sequences obtained matched previously submitted ribosomal sequences, suggesting that these isolates are potentially uncharacterized species. Comparisons of phylogenetic trees generated from the nifH sequence data and the partial 16S rRNA sequence data indicate that a conceptually similar reconstruction of evolution was provided using different genes to predict diazotrophic bacterial phylogeny. This implies that the nif genes are evolutionary ancient genes that have evolved in a similar fashion as the organisms that carry them.