The Cul3-based E3 ubiquitin ligases regulate many cellular processes using a large family of BTB domain-containing proteins as their target recognition components, but how they recognize targets remains unknown. Here we identify and characterize degrons that mediate the degradation of the Hedgehog pathway transcription factor cubitus interruptus (Ci)/Gli by Cul3-Hedghog-induced MATH and BTB domain-containing protein (HIB)/SPOP. Ci uses multiple Ser/Thr (S/T)-rich motifs that bind HIB cooperatively to mediate its degradation. We provide evidence that both HIB and Ci form dimers/oligomers and engage in multivalent interactions, which underlies the in vivo cooperativity among individual HIB-binding sites. We find that similar S/T-rich motifs are present in Gli proteins as well as in numerous HIB-interacting proteins and mediate Gli degradation by SPOP. Our results provide a mechanistic insight into how HIB/SPOP recognizes its substrates and have important implications for the genome-wide prediction of substrates for Cul3-based E3 ligases.