Living marine stromatolites at Highborne Cay, Bahamas, are formed by microbial mat communities that facilitate precipitation of calcium carbonate and bind and trap small carbonate sand grains. This process results in a laminated structure similar to the layering observed in ancient stromatolites. In the modern marine system at Highborne Cay, lamination, lithification and stromatolite formation are associated with cycling between three types of microbial communities at the stromatolite surface (Types 1, 2 and 3, which range from a leathery microbial mat to microbially fused sediment). Examination of 923 universal small-subunit rRNA gene sequences from these communities reveals that taxonomic richness increases during transition from Type 1 to Type 3 communities, supporting a previous model that proposed that the three communities represent different stages of mat development. The phylogenetic composition also changes significantly between these community types and these community changes occur in concert with variation in biogeochemical rates. The dominant bacterial groups detected in the stromatolites include Alphaproteobacteria, Planctomycetes, Cyanobacteria and Bacteroidetes. In addition, the stromatolite communities were found to contain novel cyanobacteria that may be uniquely associated with modern marine stromatolites. The implications of these findings are discussed in the context of current models for stromatolite formation.