For over 3 billion years stromatolites have been present on Earth, and thus they may represent one of the oldest and most stable forms of life. Although the best examples today of living stromatolites are found in Shark Bay, Western Australia, to date their microbiology has not been well understood. The strategic goal of this research is to investigate the morphology of modern stromatolites as the final product of complex biological and environmental interactions, by correlating the distribution of phylogenetically and physiologically defined microbial communities with prevailing ecological conditions. By analysing both culturable organisms and non-culturable populations, we discovered a wide range of cyanobacteria associated with these biogeological structures, many possessing growth characteristics consistent with their hypersaline habitat. A PCR specific for cyanobacterial 16S rDNA was employed, the resulting amplicons sequenced, and data used to infer relatedness with known cyanobacteria. The cyanobacterial community was characterised by organisms with closest identity to the genera Synechococcus, Xenococcus, Microcoleus, Leptolyngbya, Plectonema, Symploca, Cyanothece, Pleurocapsa, Prochloron, and Nostoc. For the first time in the Shark Bay stromatolites, we also identified putative salt tolerance mechanisms. Hypersalinity appears to be a factor of prime importance in the development of these stromatolites, and this is reflected in the types of microorganisms we have identified. The data here provides us with a better understanding of the microbial diversity of these unique ecosystems, and is critical for the conservation of Shark Bay as well as  the assessment of planetary exobiology.