Early lineage-specific master regulators are essential for the specification of cell types. However, once cells are committed to a specific fate, it is critical to restrict the activity of such factors to enable differentiation. To date, it remains unclear how these factors are silenced. Using the Drosophila mesoderm as a model and a comparative genomic approach, we identify the Hox transcription factor Ultrabithorax (Ubx) to be critical for the repression of the master regulator Twist. Mesoderm-specific Ubx loss-of-function experiments using CRISPR-Cas9 and overexpression studies demonstrate that Ubx majorly impacts twist transcription. A mechanistic analysis reveals that Ubx requires the NK-homeodomain protein Tinman to bind to the twist promoter. Furthermore, we find these factor interactions to be critical for silencing by recruiting the Polycomb DNA binding protein Pleiohomeotic. Altogether, our data reveal that Ubx is a critical player in mediating the silencing of Twist, which is crucial for coordinated muscle differentiation.