DNA methylation and histone modifications play an important role in transcription regulation. In cancer cells, many promoters become aberrantly methylated through the activity of the de novo DNA methyltransferases DNMT3a and DNMT3b and acquire repressive chromatin marks. NEDD8 is a ubiquitin-like protein modifier that is conjugated to target proteins, such as cullins, to regulate their activity, and cullin 4A (CUL4A) in its NEDD8-modified form is essential for repressive chromatin formation. We found that DNMT3b associates with NEDD8-modified proteins. Whereas DNMT3b interacts directly in vitro with NEDD8, conjugation of NEDD8 to target proteins enhances this interaction in vivo. DNMT3b immunoprecipitated two major bands of endogenously NEDDylated proteins at the size of NEDDylated cullins, and indeed DNMT3b interacted with CUL1, CUL2, CUL3, CUL4A, and CUL5. Moreover, DNMT3b preferentially immunoprecipitated the NEDDylated form of endogenous CUL4A. NEDD8 enhanced DNMT3b-dependent DNA methylation. Chromatin immunoprecipitation assays suggest that DNMT3b recruits CUL4A and NEDD8 to chromatin, whereas deletion of Dnmt3b reduces the association of CUL4A and NEDD8 at a repressed promoter in a cancer cell line.