The genes of the homeotic complex (HOX) encode DNA binding homeodomain proteins that control developmental fates by differentially regulating the transcription of downstream target genes. Despite their unique in vivo functions, disparate HOX proteins often bind to very similar DNA sequences in vitro. Thus, a critical question is how HOX proteins select the correct sets of target genes in vivo. The homeodomain proteins encoded by the Drosophila extradenticle gene and its mammalian homologues, the pbx genes, contribute to HOX specificity by cooperatively binding to DNA with HOX proteins. For example, the HOX protein labial cooperatively binds with extradenticle protein to a 20-bp oligonucleotide that is sufficient to direct a labial-like expression pattern in Drosophila embryos. Here we have analyzed the protein-DNA interactions that are important for forming the labial-extradenticle-DNA complex. The data suggest a model in which labial and extradenticle, separated by only 4 bp, bind this DNA as a heterodimer in a head-to-tail orientation. We have confirmed several aspects of this model by characterizing extradenticle-HOX binding to mutant oligonucleotides. Most importantly, mutations in base pairs predicted to contact the HOX N-terminal arm resulted in a change in HOX preference in the heterodimer, from labial to Ultrabithorax. These results demonstrate that extradenticle prefers to bind cooperatively with different HOX proteins depending on subtle differences in the heterodimer binding site.