Physical activity and dietary behavior changes are important to both the primary prevention and secondary management of the majority of our most prevalent chronic conditions (i.e., cardiovascular disease, hypertension, type 2 diabetes, breast and colon cancer). With over 85% of Australian adults visiting a general practitioner each year, the general practice setting has enormous potential to facilitate wide scale delivery of health behaviour interventions. However, there are also many barriers to delivery in such settings, including lack of time, training, resources and remuneration. Thus there is an important need to evaluate other feasible and effective means of delivering evidence-based physical activity and dietary behaviour programs to patients in primary care, including telephone counseling interventions. Using a cluster randomized design with practice as the unit of randomization, this study evaluated a telephone-delivered intervention for physical activity and dietary change targeting patients with chronic conditions (type 2 diabetes or hypertension) recruited from primary care practices in a socially disadvantaged community in Queensland, Australia. Ten practices were randomly assigned to the telephone intervention or to usual care, and 434 patients were recruited. Patients in intervention practices received a workbook and 18 calls over 12 months. Assessment at baseline, 4-, 12- and 18-months allows for assessment of initial change and maintenance of primary outcomes (physical activity and dietary behavior change) and secondary outcomes (quality of life, cost-effectiveness, support for health behavior change). This effectiveness trial adds to the currently limited number of telephone-delivered intervention studies targeting both physical activity and dietary change. It also addresses some of the shortcomings of previous trials by targeting patients from a disadvantaged community, and by including detailed reporting on participant representativeness, intervention implementation and cost-effectiveness, as well as an evaluation of maintenance of health behavior change.