Land plants (embryophytes) came about in a momentous evolutionary singularity: plant terrestrialization. This event marks not only the conquest of land by plants but also the massive radiation of embryophytes into a diverse array of novel forms and functions. The unique suite of traits present in the earliest land plants is thought to have been ushered in by a burst genomic novelty. Here, we asked the question of how these bursts were possible. For this, we used phylostratigraphy to explore the (i) initial emergence and (ii) reshuffling of domains to give rise to hallmark environmental response genes of land plants. We pinpoint that a quarter of the embryophytic stress physiology is specific to the lineage, yet a significant portion of this novelty arises not de novo but from re-shuffling and recombining of pre-existing domains. Our data suggest that novel combinations of old genomic substrates shaped the plant terrestrialization toolkit, including hallmark processes in signaling, biotic interactions, and specialized metabolism.