Ubiquitin-specific proteases (USPs) USP15 and USP4 belong to a subset of USPs featuring an N-terminal tandem domain in USP (DUSP) and ubiquitin-like (UBL) domain. Squamous cell carcinoma antigen recognized by T-cell 3 (SART3), a spliceosome recycling factor, binds to the DUSP-UBL domain of USP15 and USP4, recruiting them to the nucleus from the cytosol to control deubiquitination of histone H2B and spliceosomal proteins, respectively. To provide structural insight, we solved crystal structures of SART3 in the apo-form and in complex with the DUSP-UBL domain of USP15 at 2.0 and 3.0 Å, respectively. Structural analysis reveals SART3 contains 12 half-a-tetratricopeptide (HAT) repeats, organized into two subdomains, HAT-N and HAT-C. SART3 dimerizes through the concave surface of HAT-C, whereas the HAT-C convex surface binds USP15 in a novel bipartite mode. Isothermal titration calorimetry measurements and mutagenesis analysis confirmed key residues of USP15 involved in the interaction and indicated USP15 binds 20-fold stronger than USP4.