Ubiquitination plays a major role in protein degradation. Although phosphorylation-dependent ubiquitination is well known for the regulation of protein stability, methylation-dependent ubiquitination machinery has not been characterized. Here, we provide evidence that methylation-dependent ubiquitination is carried out by damage-specific DNA binding protein 1 (DDB1)/cullin4 (CUL4) E3 ubiquitin ligase complex and a DDB1-CUL4-associated factor 1 (DCAF1) adaptor, which recognizes monomethylated substrates. Molecular modeling and binding affinity studies reveal that the putative chromo domain of DCAF1 directly recognizes monomethylated substrates, whereas critical binding pocket mutations of the DCAF1 chromo domain ablated the binding from the monomethylated substrates. Further, we discovered that enhancer of zeste homolog 2 (EZH2) methyltransferase has distinct substrate specificities for histone H3K27 and nonhistones exemplified by an orphan nuclear receptor, RORα. We propose that EZH2-DCAF1/DDB1/CUL4 represents a previously unrecognized methylation-dependent ubiquitination machinery specifically recognizing "methyl degron"; through this, nonhistone protein stability can be dynamically regulated in a methylation-dependent manner.