Background This study will test the uptake and effectiveness of a flexible package of smoking cessation support provided primarily by the practice nurse (PN) and tailored to meet the needs of a diversity of patients. Methods/Design This study is a cluster randomised trial, with practices allocated to one of three groups 1) Quit with Practice Nurse 2) Quitline referral 3) GP usual care. PNs from practices randomised to the intervention group will receive a training course in smoking cessation followed by access to mentoring. GPs from practices randomised to the Quitline referral group will receive information about the study and the process of written referral and GPs in the usual care group will receive information about the study. Eligible patients are those aged 18 and over presenting to their GP who are daily or weekly smokers and who are able to give informed consent. Patients on low incomes in all three groups will be able to access free nicotine patches. Primary outcomes are sustained abstinence and point prevalence abstinence at the three month and 12 month follow-up points; and incremental cost effectiveness ratios at 12 months. Process evaluation on the reach and acceptability of the intervention approached will be collected through Computer Assisted Telephone Interviews (CATI) with patients and semi-structured interviews with PNs and GPs. The primary analysis will be by intention to treat. Cessation outcomes will be compared between the three arms at three months and 12 month follow-up using multiple logistic regression. The incremental cost effectiveness ratios will be estimated for the 12 month quit rate for the intervention groups compared to usual care and to each other. Analysis of qualitative data on process outcomes will be based on thematic analysis. Discussion High quality evidence on effectiveness of practice nurse interventions is needed to inform health policy on development of practice nurse roles. If effective, flexible support from the PN in partnership with the GP and the Quitline could become the preferred model for providing smoking cessation advice in Australian general practice.