Prostate cancer is a common cause of death worldwide. Here, we isolated cancer stem cells (CSCs) from four adenocarcinomas of the prostate (Gleason scores from 3 + 3 up to 4 + 5). CSCs were characterized by the expression of the stem cell markers TWIST, the epithelial cell adhesion molecule (EPCAM), the transcription factors SNAI1 (SNAIL) and SNAI2 (SLUG) and cancer markers such as CD44 and prominin-1 (CD133). All investigated CSC populations contained a fraction highly positive for aldehyde dehydrogenase (ALDH) function and displayed robust expressions of programmed cell death 1 (PD-1) ligands. Furthermore, we investigated immunotherapeutic approaches but had no success even with the clinically used PD-1 inhibitor pembrolizumab. In addition, we studied another death-inducing pathway via interferon gamma signaling and detected high-level upregulations of human leukocyte antigen A (HLA-A) and beta 2-microglobulin (B2M) with only moderate killing efficacy. To examine further killing mechanisms in prostate cancer stem cells (PCSCs), we analyzed NF-κB signaling. Surprisingly, two patient-specific populations of PCSCs were found: one with canonical NF-κB signaling and another one with blunted NF-κB activation, which can be efficiently killed by tumor necrosis factor (TNF). Thus, culturing of PCSCs and analysis of respective NF-κB induction potency after surgery might be a powerful tool for optimizing patient-specific treatment options, such as the use of TNF-inducing chemotherapeutics and/or NF-κB inhibitors.