Colonization of land by plants was a major transition on Earth, but the developmental and genetic innovations required for this transition remain unknown. Physiological studies and the fossil record strongly suggest that the ability of the first land plants to form symbiotic associations with beneficial fungi was one of these critical innovations. In angiosperms, genes required for the perception and transduction of diffusible fungal signals for root colonization and for nutrient exchange have been characterized. However, the origin of these genes and their potential correlation with land colonization remain elusive. A comprehensive phylogenetic analysis of 259 transcriptomes and 10 green algal and basal land plant genomes, coupled with the characterization of the evolutionary path leading to the appearance of a key regulator, a calcium- and calmodulin-dependent protein kinase, showed that the symbiotic signaling pathway predated the first land plants. In contrast, downstream genes required for root colonization and their specific expression pattern probably appeared subsequent to the colonization of land. We conclude that the most recent common ancestor of extant land plants and green algae was preadapted for symbiotic associations. Subsequent improvement of this precursor stage in early land plants through rounds of gene duplication led to the acquisition of additional pathways and the ability to form a fully functional arbuscular mycorrhizal symbiosis.