The homeodomain proteins encoded by the Hox complex genes do not bind DNA with high specificity. In vitro, Hox specificity can be increased by binding to DNA cooperatively with the homeodomain protein extradenticle or its vertebrate homologs, the pbx proteins (together, the PBC family). Here we show that a two basepair change in a Hox-PBC binding site switches the Hox-dependent expression pattern generated in vivo, from labial to Deformed. The change in vivo correlates with an altered Hox binding specificity in vitro. Further, we identify similar Deformed-PBC binding sites in the Deformed and Hoxb-4 genes and show that they generate Deformed or Hoxb-4 expression patterns in Drosophila and mouse embryos, respectively. These results suggest a model in which Hox-PBC binding sites play an instructive role in Hox specificity by promoting the formation of different Hox-PBC heterodimers in vivo. Thus, the choice of Hox partner, and therefore Hox target genes, depends on subtle differences between Hox-PBC binding sites.