The ability of fungi to form mycorrhizas with plants is one of the most remarkable and enduring adaptations to life on land. The occurrence of mycorrhizas is now well established in c. 85% of extant plants, yet the geological record of these associations is sparse. Fossils preserved under exceptional conditions provide tantalizing glimpses into the evolutionary history of mycorrhizas, showing the extent of their occurrence and aspects of their evolution in extinct plants. The fossil record has important roles to play in establishing a chronology of when key fungal associations evolved and in understanding their importance in ecosystems through time. Together with calibrated phylogenetic trees, these approaches extend our understanding of when and how groups evolved in the context of major environmental change on a global scale. Phylogenomics furthers this understanding into the evolution of different types of mycorrhizal associations, and genomic studies of both plants and fungi are shedding light on how the complex set of symbiotic traits evolved. Here we present a review of the main phases of the evolution of mycorrhizal interactions from palaeontological, phylogenetic and genomic perspectives, with the aim of highlighting the potential of fossil material and a geological perspective in a cross-disciplinary approach.