The protein stability and chromatin functions of UHRF1 (ubiquitin-like, containing PHD and RING finger domains, 1) are regulated in a cell-cycle-dependent manner. We report a structural characterization of the complex between UHRF1 and the deubiquitinase USP7. The first two UBL domains of USP7 bind to the polybasic region (PBR) of UHRF1, and this interaction is required for the USP7-mediated deubiquitination of UHRF1. Importantly, we find that the USP7-binding site of the UHRF1 PBR overlaps with the region engaging in an intramolecular interaction with the N-terminal tandem Tudor domain (TTD). We show that the USP7-UHRF1 interaction perturbs the TTD-PBR interaction of UHRF1, thereby shifting the conformation of UHRF1 from a TTD-"occluded" state to a state open for multivalent histone binding. Consistently, introduction of a USP7-interaction-defective mutation to UHRF1 significantly reduces its chromatin association. Together, these results link USP7 interaction to the dynamic deubiquitination and chromatin association of UHRF1.