Despite tremendous body form diversity in nature, bilaterian animals share common sets of developmental genes that display conserved expression patterns in the embryo. Among them are the Hox genes, which define different identities along the anterior–posterior axis. Hox proteins exert their function by interaction with TALE transcription factors. Hox and TALE members are also present in some but not all non-bilaterian phyla, raising the question of how Hox–TALE interactions evolved to provide positional information. By using proteins from unicellular and multicellular lineages, we showed that these networks emerged from an ancestral generic motif present in Hox and other related protein families. Interestingly, Hox-TALE networks experienced additional and extensive molecular innovations that were likely crucial for differentiating Hox functions along body plans. Together our results highlight how homeobox gene families evolved during eukaryote evolution to eventually constitute a major patterning system in Eumetazoans.