Beneficial associations between plants and arbuscular mycorrhizal fungi play a major role in terrestrial environments and in the sustainability of agroecosystems. Proteins, microRNAs, and small molecules have been identified in model angiosperms as required for the establishment of arbuscular mycorrhizal associations and define a symbiotic 'toolkit' used for other interactions such as the rhizobia-legume symbiosis. Based on recent studies, we propose an evolutionary framework for this toolkit. Some components appeared recently in angiosperms, whereas others are highly conserved even in land plants unable to form arbuscular mycorrhizal associations. The exciting finding that some components pre-date the appearance of arbuscular mycorrhizal fungi suggests the existence of unknown roles for this toolkit and even the possibility of symbiotic associations in charophyte green algae.