HOIL-1L and its binding partner HOIP are essential components of the E3-ligase complex that generates linear ubiquitin (Ub) chains, which are critical regulators of NF-κB activation. Using crystallographic and mutational approaches, we characterize the unexpected structural basis for the specific interaction between the Ub-like domain (UBL) of HOIL-1L and the Ub-associated domain (UBA) of HOIP. Our data indicate the functional significance of this non-canonical mode of UBA-UBL interaction in E3 complex formation and subsequent NF-κB activation. This study highlights the versatility and specificity of protein-protein interactions involving Ub/UBLs and their cognate proteins.