Purpose Cancer survivors are at increased risk for cardiovascular disease, diabetes, osteoporosis, and second primary tumors. Healthful lifestyle practices may improve the health and well-being of survivors. The FRESH START trial tested the efficacy of sequentially tailored versus standardized mailed materials on improving cancer survivors’ diet and exercise behaviors. Methods Five hundred forty-three individuals with newly diagnosed locoregional breast or prostate cancer were recruited from 39 states and two provinces within North America. Participants were randomly assigned either to a 10-month program of tailored mailed print materials promoting fruit and vegetable (F&V) consumption, reducing total/saturated fat intake, and/or increasing exercise or to a 10-month program of nontailored mailed materials on diet and exercise available in the public domain. Telephone surveys conducted at baseline and 1 year assessed body mass index (BMI), dietary consumption, physical activity, and other psychosocial/behavioral indices. Clinical assessments were conducted on a 23% subsample; information was used to validate self-reports. Results Five hundred nineteen participants completed the 1-year follow-up (4.4% attrition; sample characteristics: 57 ± 10.8 years old, 83% white, 56% female, 64% overweight/obese, and 0% underweight). Although both arms significantly improved their lifestyle behaviors (P < .05), significantly greater gains occurred in the FRESH START intervention versus the control arm (practice of two or more goal behaviors: +34% v +18%, P < .0001; exercise minutes per week: +59.3 v +39.2 minutes, P = .02; F&V per day: +1.1 v +0.6 servings, P = .01; total fat: −4.4% v –2.1%, P < .0001; saturated fat: −1.3% v –0.3%, P < .0001; and BMI: −0.3 v +0.1 kg/m², respectively, P = .004). Conclusion Mailed material interventions, especially those that are tailored, are effective in promoting healthful lifestyle changes among cancer survivors. Further study is needed to determine sustainability, cost to benefit, and generalizability to other cancer populations.