Hox genes are major regulators of embryonic development. One of their most conserved functions is to coordinate the formation of specific body structures along the anterior-posterior (AP) axis in Bilateria. This architectural role was at the basis of several morphological innovations across bilaterian evolution. In this review, we traced the origin of the Hox patterning system by considering the partnership with PBC and Meis proteins. PBC and Meis belong to the TALE-class of homeodomain-containing transcription factors and act as generic cofactors of Hox proteins for AP axis patterning in Bilateria. Recent data indicate that Hox proteins acquired the ability to interact with their TALE partners in the last common ancestor of Bilateria and Cnidaria. These interactions relied initially on a short peptide motif called hexapeptide (HX), which is present in Hox and non-Hox protein families. Remarkably, Hox proteins can also recruit the TALE cofactors by using specific PBC Interaction Motifs (SPIMs). We describe how a functional Hox/TALE patterning system emerged in eumetazoans through the acquisition of SPIMs. We anticipate that interaction flexibility could be found in other patterning systems, being at the heart of the astonishing morphological diversity observed in the animal kingdom.