Symbioses between cyanobacteria and lichen-forming fungi occur worldwide in a wide range of terrestrial environments, ranging from tropical rainforests to hot and cold deserts. The evolutionary success of these symbioses is evident from the wide range of fungal groups that have established associations with cyanobacteria. The diversity of symbiotic cyanobacteria is also high, and it is obvious that symbioses between different cyanobacteria and different lichen-forming fungi have evolved on multiple occasions. From the late 1990s cyanobacterial lichens have been the subject of a steadily increasing number of molecular investigations. This chronological review examines how these studies have contributed to present knowledge and highlights some conceptual developments that have been instrumental in the process.