The biological nature of some symbioses is unclear because it is often not easy to discern whether the symbionts obtain any benefits from the association. Mastodia tessellata, a symbiosis between a leafy green alga and a fungus of uncertain phylogenetic position, is among the most investigated, controversial, and poorly understood associations. Because it has been difficult to determine whether this association is mutually beneficial or parasitic, not all scientists accept M. tessellata as a true lichen symbiosis. Mastodia tessellata is thus an interesting model to illustrate the interactions and processes that occur in fungal-algal symbioses. To improve our understanding of this association, we address the phylogenetic positions of the bionts involved and examine their interactions at the ultrastructural level. Examining the nuLSU and nuSSU gene regions of the mycobiont and the rbcL gene region of the photobiont, we found the fungus to be related to a group of marine species in the genus Verrucaria, family Verrucariaceae, despite its present ascription to the family Mastodiaceae. In addition, the photobiont of the symbiosis emerged as closely related to the North American species Prasiola borealis. Our electron microscopy observations provide new information on the process of fungal colonization of the algal thalli, as well as on relationships between the symbionts during different stages of colonization. The special features of this lichen symbiosis are discussed and compared with other examples of fungal symbioses in nature.