Background: Diet and obesity influence prostate cancer risk and progression–effects that may be mediated through the gut microbiome. Objective: Our aim was to explore relationships among diet, gut microbes, and Gleason sum in overweight and obese prostate cancer patients enrolled in a presurgical weight-loss trial. Design: Randomized controlled trial (NCT01886677) secondary analysis. Participants/setting: In 2013-2014, 40 prostate cancer patients in the southeastern United States were randomized and allocated equally to weight-loss and wait-list control arms while they awaited prostatectomy; stool samples were collected on a subset of 22 patients. Intervention: Registered dietitian nutritionists and exercise physiologists provided semi-weekly in-person and telephone-based guidance on calorie-restricted diets and exercise to promote an approximate weight loss of 0.91 kg/wk. Main outcome measures: Baseline and follow-up 24-hour dietary recalls were conducted and analyzed (using the Automated Self-Administered 24-hour dietary recall system; National Cancer Institute, Bethesda, MD) for macronutrients, micronutrients, and food groups. Microbiome analysis targeting the V4 region of the 16S ribosomal RNA gene was performed on fecal samples. Biopsy Gleason sum data were accessed from diagnostic pathology reports. Statistical analyses performed: Associations between dietary factors and operational taxonomic units were determined by β-diversity analysis. Wilcoxon signed rank, and Mann-Whitney U testing assessed within- and between-arm differences. Associations between Gleason sum and operational taxonomic units, and diet and operational taxonomic units, were analyzed using Spearman correlations. Results: At baseline, Proteobacteria (median 0.06, interquartile range 0.01 to 0.16) were abundant, with four orders positively associated with Gleason sum. Gleason sum was associated with Clostridium (ρ=.579; P=0.005) and Blautia (ρ=−0.425, P=0.049). Increased red meat consumption from baseline was associated with Prevotella (ρ=−.497; P=0.018) and Blautia (ρ=.422; P=0.039). Men who increased poultry intake had decreased Clostridiales abundance (P=0.009). Conclusions: This hypothesis-generating study provides a starting point for investigating the relationships between the fecal microbiome, diet, and prostate cancer. Adequately powered studies are required to further explore and validate these findings.