Background: Healthy Living after Cancer (HLaC) was a national dissemination and implementation study of an evidence-based lifestyle intervention for cancer survivors. The program was imbedded into existing telephone cancer information and support services delivered by Australian state-based Cancer Councils (CC). We report here the reach, effectiveness, adoption, implementation, and maintenance of the program. Methods: In this phase IV study (single-group, pre-post design) participants-survivors of any type of cancer, following treatment with curative intent-received up to 12 nurse/allied health professional-led telephone health coaching calls over 6 months. Intervention delivery was grounded in motivational interviewing, with emphasis on evidence-based behaviour change strategies. Using the RE-AIM evaluation framework, primary outcomes were reach, indicators of program adoption, implementation, costs and maintenance. Secondary (effectiveness) outcomes were participant-reported anthropometric, behavioural and psychosocial variables including: Weight; physical activity; dietary intake; quality-of-life; treatment side-effects; distress; and fear of cancer recurrence and participant satisfaction. Changes were evaluated using linear mixed models, including terms for timepoint (0/6 months), strata (Cancer Council), and timepoint x strata. Results: Four of 5 CCs approached participated in the study. In total, 1183 cancer survivors were referred (mostly via calls to the Cancer Council telephone information service). Of these, 90.4% were eligible and 88.7% (n = 791) of those eligible consented to participate. Retention rate was 63.4%. Participants were mostly female (88%), aged 57 years and were overweight (BMI = 28.8 ± 6.5 kg/m2). Improvements in all participant-reported outcomes (standardised effect sizes of 0.1 to 0.6) were observed (p < 0.001). The program delivery costs were on average AU$427 (US$296) per referred cancer survivor. Conclusions: This telephone-delivered lifestyle intervention, which was feasibly implemented by Cancer Councils, led to meaningful and statistically significant improvements in cancer survivors' health and quality-of-life at a relatively low cost. Trial registration: Australian and New Zealand Clinical Trials Registry (ANZCTR)-ACTRN12615000882527 (registered on 24/08/2015).