Although identification of substrates for ubiquitin ligase (E3) is important for understanding its biological functions, detection of the interaction between an E3 and its substrates has remained challenging. We recently developed a new approach, termed differential proteomics-based identification of ubiquitylation substrates (DiPIUS), for the discovery of substrates of a given E3 ligase. We have now applied this approach to an uncharacterized human F-box protein, FBXO21, which serves as the substrate-recognition subunit of a SKP1-CUL1-F-box protein (SCF)-type E3, thereby identifying EID1 (EP300-interacting inhibitor of differentiation 1) as a candidate substrate. The central and COOH-terminal portion of FBXO21 was found to interact with the COOH-terminal region of EID1 in transfected cells. Over-expression of FBXO21 resulted in the down-regulation of EID1, whereas disruption of the FBXO21 gene with the CRISPR/Cas9 system stabilized EID1 and led to its accumulation in both the cytoplasm and nucleus. An in vitro ubiquitylation assay showed that EID1 is a direct substrate of SCF(FBXO)(21). Collectively, our results suggest that EID1 is a bona fide substrate of FBXO21 and that the control of EID1 abundance by SCF(FBXO)(21) might affect the transcriptional repression activity of EID1.