The filamentous, non-heterocystous cyanobacterium Microcoleus chthonoplastes is a cosmopolitan organism, known to build microbial mats in a variety of different environments. Although most of these cyanobacterial mats are known for their capacity to fix dinitrogen, M. chthonoplastes has not been assigned as a diazotrophic organism. None of the strains that were correctly identified as M. chthonoplastes has been shown to fix dinitrogen and it has repeatedly been reported that these organisms lacked the cyanobacterial nifH, the structural gene for dinitrogenase reductase. In this study, we show that a complete nif-gene cluster is present in the genome of M. chthonoplastes PCC 7420 and that the three structural nitrogenase genes, nifHDK, are present in a collection of axenic strains of M. chthonoplastes from distant locations. Phylogenetic analysis of nifHDK revealed that they cluster with the Deltaproteobacteria and that they are closely related to Desulfovibrio. The nif operon is flanked by typical cyanobacterial genes, suggesting that it is an integral part of the M. chthonoplastes genome. In this study, we provide evidence that the nif operon of M. chthonoplastes is acquired through horizontal gene transfer. Moreover, the presence of the same nif-cluster in M. chthonoplastes isolates derived from various sites around the world suggests that this horizontal gene transfer event must have occurred early in the evolution of M. chthonoplastes. We have been unable to express nitrogenase in cultures of M. chthonoplastes, but we show that these genes were expressed under natural conditions in the field.