Little is known about the taxonomic diversity of cyanobacteria in deserts, despite their important ecological roles in these ecosystems. In this study, cyanobacterial strains from the Atacama, Colorado, and Mojave Deserts were isolated and characterized using molecular, morphological, and ecological information. Phylogenetic placement of these strains was revealed through Bayesian and parsimony-based phylogenetic analyses utilizing sequences of the 16S rRNA gene and the associated 16S23S ITS region. Based on the combined evidence of this polyphasic approach, a new species from desert soils morphologically corresponding to the genus Trichocoleus was described. Trichocoleus desertorum sp. nov. Mühlsteinová, Johansen et Pietrasiak was used to obtain a phylogenetic reference point for Trichocoleus, a genus so far characterized by morphological description only. Through characterization of this new taxon in desert soils we hope to contribute to the general understanding of cyanobacterial diversity in extreme arid habitats.