Metastatic or recurrent tumors are the primary cause of cancer-related death. For prostate cancer, patients diagnosed with local disease have a 99% 5-year survival rate; however, this 5-year survival rate drops to 28% in patients with metastatic disease. This dramatic decline in survival has driven interest in discovering new markers able to identify tumors likely to recur and in developing new methods to prevent metastases from occurring. Biomarker discovery for aggressive tumor cells includes attempts to identify cancer stem cells (CSCs). CSCs are defined as tumor cells capable of self-renewal and regenerating the entire tumor heterogeneity. Thus, it is hypothesized that CSCs may drive primary tumor aggressiveness, metastatic colonization, and therapeutic relapse. The ability to identify these cells in the primary tumor or circulation would provide prognostic information capable of driving prostate cancer treatment decisions. Further, the ability to target these CSCs could prevent tumor metastasis and relapse after therapy allowing for prostate cancer to finally be cured. Here, we will review potential CSC markers and highlight evidence that describes how cells expressing each marker may drive prostate cancer progression, metastatic colonization and growth, tumor recurrence, and resistance to treatment.