Four microbial mat-forming, non-axenic, strains of the non-heterocystous, filamentous, cyanobacterial genus Microcoleus were maintained in culture and examined for the ability to fix atmospheric nitrogen (N2). Each was tested for nitrogenase activity using the acetylene reduction assay (ARA) and for the presence of the dinitrogenase reductase gene (nifH), an essential gene for N2 fixation, using the polymerase chain reaction (PCR). The Microcoleus spp. cultures were incapable of growth without an exogenous nitrogen source and never exhibited nitrogenase activity. Attempts to amplify a 360-bp segment of the nifH gene using DNA purified from the cyanobacterial cultures did not produce any cyanobacteria-specific nifH sequences. However, several non-cyanobacterial homologous nifH sequences were obtained. Phylogenetic analysis showed these sequences to be most similar to sequences from heterotrophic bacteria isolated from a marine microbial mat in Tomales Bay (California, USA), and bulk DNA extracted from a cryptobiotic soil crust in Moab (Utah, USA). Microcoleus spp. dominated the biomass of both systems. Cyanobacteria-specific 16S rDNA sequences obtained from the cultured cyanobacterial strains demonstrate that the lack of cyanobacteria-specific nifH sequences was not due to inefficiency of extracting Microcoleus DNA. Hence, both the growth and genetic data indicate that, contrary to earlier reports, Microcoleus spp. appear incapable of fixing N2 because they lack at least one of the requisite genes for this process. Furthermore, our study suggests epiphytic N2-fixing bacteria form a diazotrophic consortium with these Microcoleus spp. and are likely key sources of fixed N2 generated within soil crusts and marine microbial mats.