The linear ubiquitin (Ub) chain assembly complex (LUBAC) generates Met1-linked "linear" Ub chains that regulate the activation of the nuclear factor κB (NFκB) transcription factor and other processes. We recently discovered OTULIN as a deubiquitinase that specifically cleaves Met1-linked polyUb. Now, we show that OTULIN binds via a conserved PUB-interacting motif (PIM) to the PUB domain of the LUBAC component HOIP. Crystal structures and nuclear magnetic resonance experiments reveal the molecular basis for the high-affinity interaction and explain why OTULIN binds the HOIP PUB domain specifically. Analysis of LUBAC-induced NFκB signaling suggests that OTULIN needs to be present on LUBAC in order to restrict Met1-polyUb signaling. Moreover, LUBAC-OTULIN complex formation is regulated by OTULIN phosphorylation in the PIM. Phosphorylation of OTULIN prevents HOIP binding, whereas unphosphorylated OTULIN is part of the endogenous LUBAC complex. Our work exemplifies how coordination of ubiquitin assembly and disassembly activities in protein complexes regulates individual Ub linkage types.