A lifestyle-modification telephone-based service is delivered in New South Wales (NSW; the Get Healthy Information and Coaching Service (GHS)) as an important obesity-prevention, population-wide program. The present study examined referrals from general practitioners (GP) versus self-referral to the GHS in terms of risk profile and effectiveness of outcomes. The study used a pre-post test design to assess changes in outcomes within the setting of a telephone-based lifestyle-support service available to NSW adults (18+ years) who self-referred or were referred by their health practitioner and/or GP, and registered for the GHS between February 2009 and August 2013 (n = 22 183). The GHS has two service components: (1) the provision of an information kit (one off contact) on healthy eating, being physically active and achieving and/or maintaining a healthy weight; and (2) a 6-month coaching program that includes 10 telephone calls aimed at achieving and maintaining lifestyle-related goals. Sociodemographic characteristics, referral source and self-reported anthropometric (height, waist and waist circumference (WC)) and behavioural risk factor (physical activity and nutrition-related behaviours) data were collected at baseline and at 6 months. Analysis revealed that GPs effectively recruited hard-to-reach subtargets, as well as adults who are obese and have an increased WC risk. Participants in the GHS coaching program, irrespective of GHS referral source, reported a mean weight loss of -3.8 kg, a decrease in WC of -5.0 cm and increases in both fruit and vegetable consumption and physical activity. In conclusion, GPs have an important role in GHS uptake (through proactive referral or as an adjunct to practice-based interventions) because they can recruit those most at need and facilitate improvements in their patients' risk factor profiles.