Basal cell salivary neoplasms display similar cyto-morphologic features and are classified into adenoma and adenocarcinoma based on the presence or absence of tumor invasion at diagnosis. These neoplasms also share considerable phenotypic resemblance and co-exist with certain dermal adnexal tumors harboring the CYLD gene mutations inferring common genetic association. We sequenced the CYLD gene in both basal cell adenomas and adenocarcinomas and correlated the findings with CYLD, NF-κB, and β-catenin expression levels and clinicopathologic factors. Twenty mutations were identified and comprised of 3 synonymous and 17 non-synonymous (missense) types involving the coding exons of the CYLD gene. Mutations in exons 9-11 were identified in both adenomas and adenocarcinomas, while mutations in exons 12-20, encoding the USP domain, were exclusively found in carcinomas. Although no significant correlation between CYLD mutations and expression levels of CYLD, NF-κB, and β-catenin or clinicopathologic parameters was found, basal cell adenocarcinomas with multiple mutations showed reduction in CYLD protein expression and pursued aggressive clinical behavior. Our study revealed high incidence and sequential CYLD mutations in both basal cell adenoma and adenocarcinoma supporting a single neoplastic continuum for their evolution and provides evidence for potential diagnostic and therapeutic utility.