Cold stress is a major environmental stress that severely affects plant growth and crop productivity. Arabidopsis (Arabidopsis thaliana) HIGH EXPRESSION OF OSMOTICALLY RESPONSIVE GENE15 (HOS15) is a substrate receptor of the CULLIN4-based CLR4 ubiquitin E3 ligase complex, which epigenetically regulates cold tolerance by degrading HISTONE DEACETYLASE2C (HD2C) to switch from repressive to permissive chromatin structure in response to cold stress. In this study, we characterized a HOS15-binding protein, POWERDRESS (PWR), and analyzed its function in the cold stress response. PWR loss-of-function plants (pwr) showed lower expression of cold-regulated (COR) genes and sensitivity to freezing. PWR interacts with HD2C through HOS15, and cold-induced HD2C degradation by HOS15 is diminished in the pwr mutant. The association of HOS15 and HD2C to promoters of cold-responsive COR genes was dependent on PWR. Consistent with these observations, the high acetylation levels of histone H3 by cold-induced and HOS15-mediated HD2C degradation were significantly reduced in pwr under cold stress. PWR also interacts with C-repeat element-binding factor transcription factors to modulate their cold-induced binding to the promoter of COR genes. Collectively, our data signify that the PWR-HOS15-HD2C histone-modifying complex regulates the expression of COR genes and the freezing tolerance of plants.