The linear ubiquitin chain assembly complex (LUBAC) regulates immune signaling, and its function is regulated by the deubiquitinases OTULIN and CYLD, which associate with the catalytic subunit HOIP. However, the mechanism through which CYLD interacts with HOIP is unclear. We here show that CYLD interacts with HOIP via spermatogenesis-associated protein 2 (SPATA2). SPATA2 interacts with CYLD through its non-canonical PUB domain, which binds the catalytic CYLD USP domain in a CYLD B-box-dependent manner. Significantly, SPATA2 binding activates CYLD-mediated hydrolysis of ubiquitin chains. SPATA2 also harbors a conserved PUB-interacting motif that selectively docks into the HOIP PUB domain. In cells, SPATA2 is recruited to the TNF receptor 1 signaling complex and is required for CYLD recruitment. Loss of SPATA2 increases ubiquitination of LUBAC substrates and results in enhanced NOD2 signaling. Our data reveal SPATA2 as a high-affinity binding partner of CYLD and HOIP, and a regulatory component of LUBAC-mediated NF-κB signaling.