The Hedgehog (Hh) signaling pathway plays important roles in both embryonic development and adult tissue homeostasis. Such biological functions are mediated by the transcription factor Cubitus interruptus (Ci). Yet the transcriptional regulation of the effector Ci itself is poorly investigated. Through an RNAi-based genetic screen, we identified that female sterile (1) homeotic (Fsh), a transcription co-activator, directly activates Ci transcription. Biochemistry assays demonstrated physical interactions among Fsh, Sex combs extra (Sce), and Polycomb (Pc). Functional assays further showed that both Pc and Sce are required for Ci expression, which is not likely mediated by the derepression of Engrailed (En), a repressor of Ci, in Pc or Sce mutant cells. Finally, we provide evidence showing that Pc/Sce facilitates the binding of Fsh at Ci locus and that the physical interaction between Fsh and Pc is essential for Fsh-mediated Ci transcription. Taken together, we not only uncover that Ci is transcriptionally regulated by Fsh-Pc-Sce complex but also provide evidence for the coordination between Fsh and PcG proteins in transcriptional regulation.