Plant roots and root systems are indispensable for water and nutrient foraging, and are a major evolutionary achievement for plants to cope with dry land conditions. The ability of roots to branch contributes substantially to their capacity to explore the soil for water and nutrients, and led ~400 million years ago to the successful colonization of land by plants, eventually even in arid regions. During this colonization, different forms of root branching evolved, reinforcing step by step the phenotypic plasticity of the root system. Whereas the lycophytes, the most ancient land plants with roots, only branch at the root tip, ferns are able to form roots laterally in a fixed pattern along the main root. Finally, roots of seed plants show the highest phenotypic plasticity, because lateral roots can possibly, dependent on internal and/or external signals, be produced at almost any position along the main root. The competence to form lateral roots in seed plants is based on the presence of internal cell files with stem cell-like features. Despite the dissimilarities between the different clades, a number of genetic modules seem to be co-opted in order to acquire root branching capacity. In this review, starting from the lateral root pathways in seed plants, we review root branching in the different land plant lineages and discuss the hitherto described genetic modules that contribute to their root branching capacity. We try to obtain insight into how land plants have acquired an increasing root branching plasticity during evolution that contributed to the successful colonization of our planet by seed plants.