Prostate cancer is the second most common malignant cancer in males. It involves a complex process driven by diverse molecular pathways that closely related to the survival, apoptosis, metabolic and metastatic characteristics of aggressive cancer. Prostate cancer can be categorized into androgen dependent prostate cancer and castration-resistant prostate cancer and cure remains elusive due to the developed resistance of the disease. Natural compounds represent an extraordinary resource of structural scaffolds with high diversity that can offer promising chemical agents for making prostate cancer less devastating and curable. Herein, those natural compounds of different origins and structures with potential cytotoxicity and/or anti-tumor activities against prostate cancer are critically reviewed and summarized according to the cellular signaling pathways they interfere. Moreover, the anti-prostate cancer efficacy of many nutrients, medicinal plant extracts and Chinese medical formulations were presented, and the future prospects for the application of these compounds and extracts were discussed. Although the failure of conventional chemotherapy as well as involved serious side effects makes natural products ideal candidates for the treatment of prostate cancer, more investigations of preclinical and even clinical studies are necessary to make use of these medical substances reasonably. Therefore, the elucidation of structure-activity relationship and precise mechanism of action, identification of novel potential molecular targets, and optimization of drug combination are essential in natural medicine research and development.