Androgen deprivation therapy (ADT) is initial systemic therapy for advanced prostate cancer and is used as an adjuvant to local therapy for high-risk disease, but responses in advanced disease are transient. Prostate cancer stem cells are a small fraction of tumor cells that give rise to malignant cells. Initial or acquired stem cell resistance to castration must therefore underlie castrate-resistant prostate cancer. We sought to review the evidence on cancer stem cells and androgen deprivation therapy to determine if prostate cancer stem cell resistance occurs from the outset, or if it is an acquired resistance. Prostate cancer stem cells do not express androgen receptor (AR) and hence should not be directly responsive to androgen deprivation therapy. However, castrate-resistant tumors that are derived from stem cells, have molecular changes such as amplification of the androgen receptor gene, or other genetic changes resulting in gain-of-function changes in AR, implying an acquired resistance to androgen deprivation. The origins of castrate-resistant tumors, with mechanisms such as androgen receptor gene amplification from androgen receptor negative prostate cancer stem cells, is an apparent conundrum. Insight into how this occurs may lead to new treatments that overcome or delay castrate-resistance. Herein, we review the evidence on cancer stem cells, the benefits of ADT, the biological basis of response to ADT, and mechanisms of castrate-resistance. We also explore the apparent conundrum of why AR-negative prostate cancer stem cells can give rise to castrate-resistant prostate cancer. We propose possible explanations that may resolve this conundrum and discuss implications for hormonal therapy.