Hair follicle cycling is a highly regulated and dynamic cellular process consisting of phases of growth, regression, and quiescence. The hairless (hr) gene encodes a nuclear factor that is highly expressed in the skin, where it appears to be an essential regulator during the regression in the catagen hair follicle. In hairless mice, as well as humans with congenital atrichia, the absence of hr protein initiates a premature and abnormal catagen due to defects in the signaling required for hair follicle remodeling. Here, we report that hr protein is a nuclear protein that is tightly associated with the nuclear matrix scaffold. Using a series of deletion constructs of the mouse hr gene, we monitored the sub-cellular localization of the recombinant protein by in situ immunolocalization and biochemical fractionation after nuclear matrix extraction of transiently transfected cells. We identified a novel nuclear matrix-targeting signal (NMTS) in the hr protein and mapped the domain to amino acid residues 111-186 of the mouse hr sequence. Furthermore, we provide evidence that this region not only mediates the interaction of hr with components of the nuclear architecture, but also specifies the sub-nuclear location of the hr protein to nuclear domains containing deacetylase activity. The N-terminal region directs hr to a speckled nuclear pattern that co-localizes with the histone deacetylase 3 (HDAC), but not with HDAC1 or HDAC7. Based on our findings, we propose that hr protein is part of a specific multi-protein repressor complex and that hr may be involved in chromatin remodeling.