Hamelin Pool in Western Australia is one of the two major sites in the world with active marine stromatolite formation. Surrounded by living smooth and pustular mats, these ancient laminated structures are associated with cyanobacterial communities. Recent studies have identified a wide diversity of bacteria and archaea in this habitat. By understanding and evaluating the microbial diversity of this environment we can obtain insights into the formation of early life on Earth, as stromatolites have been dated in the geological record as far back as 3.5 billion years. Automated ribosomal intergenic spacer analysis (ARISA) patterns were shown to be a useful method to genetically discriminate halophilic archaea within this environment. Patterns of known halophilic archaea are consistent, by replicate analysis, and the halophilic strains isolated from stromatolites have novel intergenic spacer profiles. ARISA-PCR, performed directly on extracted DNA from different sample sites, provided significant insights into the extent of previous unknown diversity of halophilic archaea within this environment. Cloning and sequence analysis of the spacer regions obtained from stromatolites confirmed the novel and broad diversity of halophilic archaea in this environment.