Evidence-based tobacco control in ethnic minorities is compromised by the near absence of rigorous testing of interventions in either prevention or cessation. This randomised controlled trial was designed to evaluate the feasibility, acceptability and impact of a culturally specific cessation intervention delivered in the context of primary medical care in the most culturally diverse region of New South Wales. Adult Arabic smokers were recruited from practices of 29 general practitioners (GPs) in south-west Sydney and randomly allocated to usual care (n=194) or referred to six sessions of smoking cessation telephone support delivered by bilingual psychologists (n=213). Although 62.2% of participants indicated that telephone support would benefit Arabic smokers, there were no significant differences at 6 or 12 months between intervention and control groups in point prevalence abstinence rates (11.7% vs 12.9%, P=0.83; 8.4% vs 11.3%, P=0.68, respectively) or the mean shift in stage-of-change towards intention to quit. As participants and GPs found telephone support acceptable, we also discuss redesign and the unfulfilled obligation to expand the evidence base in tobacco control from which the ethnic majority already benefits.