Obesity adversely impacts overall and cancer-specific survival among breast cancer patients. Preclinical studies demonstrate negative energy balance inhibits cancer progression; however, feasibility and effects in patients are unknown. A two-arm, single-blinded, randomized controlled weight-loss trial was undertaken presurgery among 32 overweight/obese, Stage 0–II breast cancer patients. The attention control arm (AC) received basic nutritional counseling and upper-body progressive resistance training whereas the weight loss intervention (WLI) arm received identical guidance, plus counseling on caloric restriction and aerobic exercise to promote 0.68–0.92 kg/week weight loss. Anthropometrics, body composition, blood and survey data were collected at baseline and presurgery ∼30 days later. Tumor markers (e.g., Ki67) and gene expression were assessed on biopsy and surgical specimens; sera were analyzed for cytokines, growth and metabolic factors. Significant WLI vs. AC differences were seen in baseline-to-follow-up changes in weight (−3.62 vs. −0.52 kg), %body fat (−1.3 vs. 0%), moderate-to-vigorous physical activity (+224 vs. +115 min/week), caloric density (−0.3 vs. 0 kcal/g), serum leptin (−12.3 vs. −4.0 ng/dl) and upregulation of tumor PI3Kinase signaling and cell cycle-apoptosis related genes (CC-ARG; all p-values <0.05). Cytolytic CD56dimNK cell expression was positively associated with weight loss; CC-ARG increased with physical activity. Increased tumor (nuclear) TNFα and IL-1β, CX3CL1 and CXCL1 gene expression was observed in the WLI. Tumor Ki67 did not differ between arms. Feasibility benchmarks included 80% accrual, 100% retention, no adverse effects and excellent adherence. Short-term weight loss interventions are feasible; however, mixed effects on tumor biology suggest unclear benefit to presurgical caloric restriction, but possible benefits of physical activity.