CYLD is a tumor suppressor gene related to cylindroma and is negative regulator of NF-kappaB. However, antitumor effect of CYLD has not been reported. The activation of NF-kappaB induced by tumor necrosis factor-related apoptosis-inducing ligand (TRAIL) renders hepatocellular carcinoma (HCC) resistant to TRAIL-mediated cell apoptosis. Here we described that the adenoviral vector expressing CYLD (Ad/hTERT-CYLD) augmented the cytotoxicity of TRAIL in HCC cells by negatively regulating NF-kappaB activity since CYLD could reverse the ubiquitination of TNF receptor-associated factor 2 (TRAF2) and interact with the IkappaB kinasegamma (IKKgamma). The combined treatment of Ad/hTERT-CYLD and a conditionally replicating adenovirus carrying TRAIL gene (ZD55-TRAIL) induced rapid and potent apoptosis in HCC cells, characterized by activation of caspase-3, caspase-8, PARP and the reduction of X-linked inhibitor of apoptosis protein (XIAP). In animal study, the combined treatment could eradicate the BEL7404 xenograft tumors. In contrast, treatment with Ad/hTERT-CYLD or ZD55-TRAIL alone achieved less antitumor effect. CYLD inhibits TRAIL-mediated NF-kappaB activation and enhances the sensitivity of HCC cells to TRAIL-triggered apoptosis. The combined delivery of Ad/hTERT-CYLD and ZD55-TRAIL may be a new useful strategy for HCC or other tumor cells with enhanced NF-kappaB activity.