The 16S-rDNA from 22 cyanobacteria isolated from biofilms on walls of modern and historic buildings in Brazil was partially sequenced (approximately 350 bp) using specific primers. The cyanobacteria with the closest matching sequences were found using the BLAST tool. The sequences were combined with 52 other cyanobacterial sequences already deposited in public data banks and a dendrogram constructed, after deletion from each sequence of one of the variable 16S rDNA regions (VI). The newly sequenced organisms fitted well within their respective families, but their similarities to other members of the groups were generally low, less than 96%. Close matches were found only with one other terrestrial (hot dry desert) cyanobacterium, Microcoleus sociatus, and with Anabaena variabilis. Phylogenetic analysis suggested that the deletion of the hypervariable regions in the RNA structure is essential for meaningful evolutionary studies. The results support the standard phylogenetic tree based on morphology, but suggest that these terrestrial cyanobacteria are distant relatives of their equivalent aquatic genera and are, indeed, a distinct population.