Nuclear factor-kappa B (NF-kappaB) is a critical regulator of multiple biological functions including innate and adaptive immunity and cell survival. Activation of NF-kappaB is tightly regulated to preclude chronic signaling that may lead to persistent inflammation and cancer. Ubiquitination of key signaling molecules by E3 ubiquitin ligases has emerged as an important regulatory mechanism for NF-kappaB signaling. Deubiquitinases (DUBs) counteract E3 ligases and therefore play a prominent role in the downregulation of NF-kappaB signaling and homeostasis. Understanding the mechanisms of NF-kappaB downregulation by specific DUBs such as A20 and CYLD may provide therapeutic opportunities for the treatment of chronic inflammatory diseases and cancer.