The deubiquitinating enzyme BRCA1-associated protein 1 (BAP1) possesses growth inhibitory activity and functions as a tumor suppressor. In this study we report that BAP1 also plays positive roles in cell proliferation. BAP1 depletion by RNAi inhibits cell proliferation as does overexpression of a dominant negative mutant of BAP1. Mass spectrometry analyses of copurified proteins revealed that BAP1 is associated with factors involved in chromatin modulation and transcriptional regulation. We show that the interaction with host cell factor-1 (HCF-1), a cell-cycle regulator composed of HCF-1N and HCF-1C, is critical for the BAP1-mediated growth regulation. We found that HCF-1N is modified with Lys-48-linked polyubiquitin chains on its Kelch domain. The HCF-1 binding motif of BAP1 is required for interaction with HCF-1N and mediates deubiquitination of HCF-1N by BAP1. The importance of the BAP1-HCF-1 interaction is underscored by the fact that growth suppression by the dominant negative BAP1 mutant is entirely dependent on the HCF-1 binding motif. These results suggest that BAP1 regulates cell proliferation by deubiquitinating HCF-1.