Hox genes encode Homeodomain-containing transcription factors, which specify segmental identities along the anterior-posterior axis. Functional changes in Hox genes have been directly implicated in the evolution of body plans across the metazoan lineage. The Hox protein Ultrabithorax (Ubx) is expressed and required in developing third thoracic (T3) segments in holometabolous insects studied so far, particularly, of the order Coleoptera, Lepidoptera and Diptera. Ubx function is key to specify differential development of the second (T2) and T3 thoracic segments in these insects. While Ubx is expressed in the third thoracic segment in developing larvae of Hymenopteran Apis mellifera, the morphological differences between T2 and T3 are subtle. To identify evolutionary changes that are behind the differential function of Ubx in Drosophila and Apis, which are diverged for more than 350 million years, we performed comparative analyses of genome wide Ubx-binding sites between these two insects. Our studies reveal that a motif with a TAAAT core is a preferred binding site for Ubx in Drosophila, but not in Apis. Biochemical and transgenic assays suggest that in Drosophila, the TAAAT core sequence in the Ubx binding sites is required for Ubx-mediated regulation of two of its target genes studied here; CG13222, a gene that is normally upregulated by Ubx and vestigial (vg), whose expression is repressed by Ubx in T3. Interestingly, changing the TAAT site to a TAAAT site was sufficient to bring an otherwise unresponsive enhancer of the vg gene from Apis under the control of Ubx in a Drosophila transgenic assay. Taken together, our results suggest an evolutionary mechanism by which critical wing patterning genes might have come under the regulation of Ubx in the Dipteran lineage.