Prostate cancer (PCa) is the most frequently diagnosed cancer in men and the second most common cause of cancer-related mortality among men in the developed world. Conventional anti-PCa therapies include surgery, radiation, hormonal ablation, and chemotherapy. Despite increasing efforts, these therapies are not effective for patients with advanced and/or metastatic disease. In most cases, cancer therapies fail due to an incomplete depletion of tumor cells, resulting in tumor relapse. The cancer stem cell (CSC) hypothesis is an emerging model that explains many of the molecular characteristics of oncological disease as well as the tendency of cancers to relapse, metastasize, and develop resistance to conventional therapies. CSCs are a reservoir of cancer cells that exhibit properties of self-renewal and the ability to reestablish the heterogeneous tumor cell population. The existence of PCa stem cells offers a theoretical explanation for many uncertainties regarding PCa and also for treatment resistance and disease progression once clinical cure is achieved. Therapies targeting CSCs might therefore lead to more effective cancer treatments, divergent from a traditional anti-proliferative approach, based on tumor bulk reduction accompanied by CSC-specific inhibition. Here, we focus on reviewing the historical perspective as well as concepts regarding stem cells and CSCs in PCa. In addition, we will report possible strategies and new clinical approaches that address the CSC-based concept of tumorigenesis in PCa.