Background and aims: Smoking cessation medications are effective, but often underutilized because of costs and side effects. Cytisine is a plant-based smoking cessation medication with more than 50 years of use in central and eastern Europe. While cytisine has been found to be well-tolerated and more effective than nicotine replacement therapy, direct comparisons with varenicline have not been conducted. This study evaluates the effectiveness, safety and cost-effectiveness of cytisine compared with varenicline. Design: Two-arm, parallel group, randomized, non-inferiority trial, with allocation concealment and blinded outcome assessment. Setting: Australian population-based study. Participants: Adult daily smokers (n = 1266) interested in quitting will be recruited through advertisements and Quitline telephone-based cessation support services. Intervention and comparator: Eligible participants will be randomized (1 : 1 ratio) to receive either cytisine capsules (25-day supply) or varenicline tablets (12-week supply), prescribed in accordance with the manufacturer's recommended dosing regimen. The medication will be mailed to each participant's nominated residential address. All participants will also be offered standard Quitline behavioural support (up to six 10–12-minute sessions). Measurements: Assessments will be undertaken by telephone at baseline, 4 and 7 months post-randomization. Participants will also be contacted twice (2 and 4 weeks post-randomization) to ascertain adverse events, treatment adherence and smoking status. The primary outcome will be self-reported 6-month continuous abstinence from smoking, verified by carbon monoxide at 7-month follow-up. We will also evaluate the relative safety and cost-effectiveness of cytisine compared with varenicline. Secondary outcomes will include self-reported continuous and 7-day point prevalence abstinence and cigarette consumption at each follow-up interview. Comments: If cytisine is as effective as varenicline, its lower cost and natural plant-based composition may make it an acceptable and affordable smoking cessation medication that could save millions of lives world-wide.