Background: Obesity is associated with tumor aggressiveness and disease-specific mortality for more than 15 defined malignancies, including prostate cancer. Preclinical studies suggest that weight loss from caloric restriction and increased physical activity may suppress hormonal, energy-sensing, and inflammatory factors that drive neoplastic progression; however, exact mechanisms are yet to be determined, and experiments in humans are limited. Methods: We conducted a randomized controlled trial among 40 overweight or obese, newly-diagnosed prostate cancer patients who elected prostatectomy to explore feasibility of a presurgical weight loss intervention that promoted a weight loss of roughly one kg. week-1 via caloric restriction and physical activity, as well as to assess effects on tumor biology and circulating biomarkers. Measures of feasibility (accrual, retention, adherence, and safety) were primary endpoints. Exploratory aims were directed at the intervention's effect on tumor proliferation (Ki-67) and other tumor markers (activated caspase-3, insulin and androgen receptors, VEGF, TNFβ, NFκB, and 4E-BP1), circulating biomarkers (PSA, insulin, glucose, VEGF, TNFβ, leptin, SHBG, and testosterone), lymphocytic gene expression of corresponding factors and cellular bioenergetics in neutrophils, and effects on the gut microbiome. Consenting patients were randomized in a 1:1 ratio to either: 1) weight loss via a healthful, guidelines-based diet and exercise regimen; or 2) a wait-list control. While biological testing is currently ongoing, this paper details our methods and feasibility outcomes. Results: The accrual target was met after screening 101 cases (enrollment rate: 39.6 %). Other outcomes included a retention rate of 85 %, excellent adherence (95 %), and no serious reported adverse events. No significant differences by age, race, or weight status were noted between enrollees vs. non-enrollees. The most common reasons for non-participation were "too busy" (30 %), medical exclusions (21 %), and "distance" (16 %). Conclusions: Presurgical trials offer a means to study the impact of diet and exercise interventions directly on tumor tissue, and other host factors that are feasible and safe, though modifications are needed to conduct trials within an abbreviated period of time and via distance medicine-based approaches. Pre-surgical trials are critical to elucidate the impact of lifestyle interventions on specific mechanisms that mediate carcinogenesis and which can be used subsequently as therapeutic targets. Trial registration: NCT01886677.