Lichens, symbiotic consortia of lichen-forming fungi and their photosynthetic partners have long had an extremely poor fossil record. However, recently over 150 new lichens were identified from European Paleogene amber and here we analyse crustose lichens from the new material. Three fossil lichens belong to the extant genus Ochrolechia (Ochrolechiaceae, Lecanoromycetes) and one fossil has conidiomata similar to those produced by modern fungi of the order Arthoniales (Arthoniomycetes). Intriguingly, two fossil Ochrolechia specimens host lichenicolous fungi of the genus Lichenostigma (Lichenostigmatales, Arthoniomycetes). This confirms that both Ochrolechia and Lichenostigma already diversified in the Paleogene and demonstrates that also the specific association between the fungi had evolved by then. The new fossils provide a minimum age constraint for both genera at 34 million years (uppermost Eocene).