Introduction Primary care physicians are well placed to offer physical activity counseling, but insufficient time is a barrier. Referral to an exercise specialist is an alternative. In Australia, exercise specialists are publicly funded to provide face-to-face counseling to patients who have an existing chronic illness. This trial aimed to (1) determine the efficacy of primary care physicians’ referral of insufficiently active patients for counseling to increase physical activity, compared with usual care, and (2) compare the efficacy of face-to-face counseling with counseling predominantly via telephone. Study design Three-arm pragmatic RCT. Setting/participants Two hundred three insufficiently active primary care practice patients (mean age 57 years; 70% female) recruited in New South Wales, Australia, in 2011–2014. Intervention (1) Five face-to-face counseling sessions by an exercise specialist, (2) one face-to-face counseling session followed by four telephone calls by an exercise specialist, or (3) a generic mailed physical activity brochure (usual care). The counseling sessions operationalized social cognitive theory via a behavior change counseling framework. Main outcome measures Change in average daily step counts between baseline and 12 months. Data were analyzed in 2016. Results Forty (20%) participants formally withdrew; completion rates at 3 and 6 months were 64% and 58%, respectively. Intervention attendance was high (75% received five sessions). The estimated mean difference between usual care and the combined intervention groups at 12 months was 1,002 steps/day (95% CI=244, 1,759, p=0.01). When comparing face-to-face with predominantly telephone counseling, the telephone group had a non-significant higher mean daily step count (by 619 steps) at 12 months. Conclusions Provision of expert physical activity counseling to insufficiently active primary care patients resulted in a significant increase in physical activity (approximately 70 minutes of walking per week) at 12 months. Face-to-face only and counseling conducted predominantly via telephone were both effective. This trial provides evidence to expand public funding for expert physical activity counseling and for delivery via telephone in addition to face-to-face consultations. Trial registration This trial is registered at www.anzctr.org.au/ ACTRN12611000884909.