The spatial and temporal control of gene expression is key to generation of specific cellular fates during development. Studies of the transcriptional repressor REST/NRSF (RE1 Silencing Transcription Factor or Neural Restrictive Silencing Factor) have provided important insight into the role that epigenetic modifications play in differential gene expression. However, the precise function of REST during embryonic development is not well understood. We have discovered a novel interaction between zebrafish Rest and the Hedgehog (Hh) signaling pathway. We observed that Rest knockdown enhances or represses Hh signaling in a context-dependant manner. In wild-type embryos and embryos with elevated Hh signaling, Rest knockdown augments transcription of Hh target genes. Conversely, in contexts where Hh signaling is diminished, Rest knockdown has the opposite effect and Hh target gene expression is further attenuated. Epistatic analysis revealed that Rest interacts with the Hh pathway at a step downstream of Smo. Furthermore, we present evidence implicating the bifunctional, Hh signaling component Gli2a as key to the Rest modulation of the Hh response. The role of Rest as a regulator of Hh signaling has broad implications for many developmental contexts where REST and Hh signaling act.