Objectives: Active telephone recruitment (‘cold calling’) can enrol almost 45 times more smokers to cessation services than media. However, the effectiveness of proactive telephone counselling with cold-called smokers from the broader community is unknown. This study examined whether proactive telephone counselling improved abstinence, quit attempts and reduced cigarette consumption among cold-called smokers. Methods: From 48014 randomly selected electronic telephone directory numbers, 3008 eligible smokers were identified and 1562 (51.9%) smokers recruited into the randomised controlled trial. Of these, 769 smokers were randomly allocated to proactive telephone counselling and 793 to the control (ie, mailed self-help) conditions. Six counselling calls were offered to intervention smokers willing to quit within a month and four to those not ready to quit. The 4-month, 7-month and 13-month follow-up interviews were completed by 1369 (87.6%), 1278 (81.8%) and 1245 (79.9%) participants, respectively. Results: Proactive telephone counselling participants were significantly more likely than controls to achieve 7-day point prevalence abstinence at 4 months (13.8% vs 9.6%, p=0.005) and 7 months (14.3% vs 11.0%, p=0.02) but not at 13 months. There was a significant impact of telephone counselling on prolonged abstinence at 4 months (3.4% vs 1.8%, p=0.02) and at 7 months (2.2% vs 0.9%, p=0.02). At 4 months post recruitment, telephone counselling participants were significantly more likely than controls to have made a quit attempt (48.6% vs 42.9%, p=0.01) and reduced cigarette consumption (16.9% vs 9.0%, p=0.0002). Conclusions: Proactive telephone counselling initially increased abstinence and quitting behaviours among cold-called smokers. Given its superior reach, quitlines should consider active telephone recruitment, provided relapse can be reduced.