Basal cell carcinoma (BCC) of the prostate is a rare tumor. Compared with the more common acinar adenocarcinoma (AAC) of the prostate, BCCs show features of basal cell differentiation and are thought to be biologically distinct from AAC. The spectrum of molecular alterations of BCC has not been comprehensively described, and genomic studies are lacking. Herein, whole genome sequencing was performed on archival formalin-fixed, paraffin-embedded specimens of two cases with BCC. Prostatic BCCs were characterized by an overall low copy number and mutational burden. Recurrent copy number loss of chromosome 16 was observed. In addition, putative driver gene alterations in KIT, DENND3, PTPRU, MGA, and CYLD were identified. Mechanistically, depletion of the CYLD protein resulted in increased proliferation of prostatic basal cells in vitro. Collectively, these studies show that prostatic BCC displays distinct genomic alterations from AAC and highlight a potential role for loss of chromosome 16 in the pathogenesis of this rare tumor type.