Background: To systematically review and analyse the associations between fat and muscle mass measures with overall survival in men with prostate cancer. Methods: A systematic search was conducted in CINAHL, Cochrane Library, EMBASE, PubMed, and Web of Science databases from inception to December 2020, while abstracts from the American Society of Clinical Oncology (ASCO), Clinical Oncology Society of Australia (COSA), and the American College of Sports Medicine (ACSM) conferences were searched from 2014 to 2020. Eligible articles examined the association of body composition measures, such as fat mass (e.g., fat mass, visceral adipose tissue (VAT), subcutaneous adipose tissue (SAT), and VAT/SAT) and muscle mass measures, with overall survival in prostate cancer patients at any treatment stage. The primary endpoint was overall survival. Random-effect meta-analysis was conducted for studies reporting multivariable or univariable analysis assessing the associations of fat mass measures (i.e., fat mass, VAT, SAT, VAT/SAT) and muscle mass measures with overall survival. Results: Sixteen cohort studies that comprised 4807 men with prostate cancer were included. Total adiposity (hazard ratio (HR) 0.98, 95% CI: 0.75–1.28, p = 0.888) and VAT (HR 1.03, 95% CI: 0.74–1.43, p = 0.873) were not significantly associated with overall survival, while higher subcutaneous adipose tissue levels were associated with higher survival (HR 0.68, 95% CI: 0.54–0.84, p = 0.001). Greater mortality risk was found in patients with localised (HR 1.91, 95% CI: 1.40–2.62, p < 0.001) and advanced disease (HR 1.43, 95% CI: 1.07–1.92, p = 0.020) presenting with low levels of muscle mass compared to those presenting with high levels. Discussion: These results indicate that although overall adiposity should be cautiously interpreted in regards to survival, high muscle mass and SAT, and low VAT/SAT ratio values are associated with overall survival in men with prostate cancer.