Our previous presurgical weight loss trial among 40 prostate cancer patients found that rapid (but not slow) weight loss resulted in increased tumor Ki67 and Cathepsin L (CTSL) gene expression. In follow-up analyses, we strove to better understand these unexpected findings. A correlative study was undertaken by performing additional analyses [free fatty acids (FFAs), plasma CTSL, and inflammatory cytokines] on remaining pre-post intervention sera and exploring associations with extant data on tumor Ki67, body composition, physical activity (PA), and fecal microbiota. Positive associations were observed between changes in % body fat and FFAs (ρ = 0.428, p = 0.026), insulin (ρ = 0.432, p = 0.019), and Interleukin-6 (ρ = 0.411, p = 0.041). Change in Ki67 was inversely associated with change in lean mass (ρ = −0.912, p = 0.001) and change in insulin (ρ = −0.650, p = 0.042). Change in insulin was also associated with CTSL (ρ = −0.643, p = 0.024) and FFAs (ρ = −0.700, p = 0.016). Relative abundance of Bifidobacterium was associated with CTSL (ρ = 0.627, p = 0.039) and FFAs (ρ = 0.691, p = 0.019); Firmicutes was positively associated with change in PA (ρ = 0.830, p = 0.003). Contrary to hypotheses, FFAs decreased with systemic fat loss. Moreover, although glucose metabolism improved, it was inversely associated with Ki67 and CTSL. Lean mass loss was highly correlated with increased Ki67. The relationships between prostate tumor Ki67 and CTSL and weight loss associated changes in FFAs, lean mass, and fecal microbiota warrant further investigation.