Purpose: FRESH START is a randomized controlled trial that will test whether a personally tailored, distance-medicine-based program will increase exercise and fruit and vegetable consumption, and decrease fat intake of individuals recently diagnosed with breast or prostate cancer. Methods: Early-stage breast and prostate cancer cases (N = 530) will be identified within 9 months of diagnosis from hospital cancer registries and large oncologic practices throughout the United States. These individuals will be sent a letter of invitation and screened for eligibility. After a baseline telephone interview, participants will be randomized into one of two arms that receive materials aimed at increasing exercise and fruit and vegetable intake, and decreasing dietary fat: 1) an experimental arm that receives a workbook and a series of six 4-page newsletters delivered every 7 wk and personally tailored on type of cancer, cancer coping style, race, age, self-efficacy, stage of readiness, and barriers and/or progress toward goal behavior (i.e., ≥ 30 min of exercise at least 5 d·wk-1, ≥ 5 servings of vegetables and fruit per day, and ≤ 30% of calories from fat); or 2) a control arm that receives a series of nontailored health brochures. Follow-up interviews scheduled 1 and 2 yr postbaseline will determine short- and long-term efficacy and the effects of the interventions on other endpoints (quality of life, perceived health, etc.). Factors, such as gender, race, and social support, also will be explored to determine potential interactions with program efficacy. Conclusion: Given the growing number of cancer survivors, distance-medicine-based interventions addressing multiple behaviors and targeting this high-risk group have the potential to make a positive and broad public health impact.