Lichens are mutually symbiotic systems consisting of fungal and algal symbionts. While diverse lichen-forming fungal species are known, limited species of algae form lichens. Plasticity in the combination of fungal and algal species with different eco-physiological properties may contribute to the worldwide distribution of lichens, even in extreme habitats. Lichens have been studied systematically for more than 200 years; however, plasticity in fungal–algal/cyanobacterial symbiotic combinations is still unclear. In addition, the association between non-cyanobacterial bacteria and lichens has attracted attention in recent years. The types, diversity, and functions of lichen-associated bacteria have been studied using both culture-based and culture-independent methods. This review summarizes the history of systematic research on lichens and lichen-associated bacteria and provides insights into the current status of research in this field.