The diversity and nitrogenase activity of epilithic marine microbes in a Holocene beach rock (Heron Island, Great Barrier Reef, Australia) with a proposed biological calcification “microbialite” origin were examined. Partial 16S rRNA gene sequences from the dominant mat (a coherent and layered pink-pigmented community spread over the beach rock) and biofilms (nonstratified, differently pigmented microbial communities of small shallow depressions) were retrieved using denaturing gradient gel electrophoresis (DGGE), and a clone library was retrieved from the dominant mat. The 16S rRNA gene sequences and morphological analyses revealed heterogeneity in the cyanobacterial distribution patterns. The nonheterocystous filamentous genus Blennothrix sp., phylogenetically related to Lyngbya , dominated the mat together with unidentified nonheterocystous filaments of members of the Pseudanabaenaceae and the unicellular genus Chroococcidiopsis . The dominance and three-dimensional intertwined distribution of these organisms were confirmed by nonintrusive scanning microscopy. In contrast, the less pronounced biofilms were dominated by the heterocystous cyanobacterial genus Calothrix , two unicellular Entophysalis morphotypes, Lyngbya spp., and members of the Pseudanabaenaceae family. Cytophaga - Flavobacterium - Bacteroides and Alphaproteobacteria phylotypes were also retrieved from the beach rock. The microbial diversity of the dominant mat was accompanied by high nocturnal nitrogenase activities (as determined by in situ acetylene reduction assays). A new DGGE nifH gene optimization approach for cyanobacterial nitrogen fixers showed that the sequences retrieved from the dominant mat were related to nonheterocystous uncultured cyanobacterial phylotypes, only distantly related to sequences of nitrogen-fixing cultured cyanobacteria. These data stress the occurrence and importance of nonheterocystous epilithic cyanobacteria, and it is hypothesized that such epilithic cyanobacteria are the principal nitrogen fixers of the Heron Island beach rock.