ABSTRACTAim To assess the effectiveness of a new computer‐generated tailored advice programme designed to be used by smokers and recent quitters having problems staying stopped.Design Randomized trial comparing a series of questionnaire assessments leading to tailored computer‐generated advice letters mailed at strategically relevant times, to a no extra treatment control sent standardized printed self‐help materials.Setting Victoria, Australia.Participants A total of 1058 smokers or recent quitters recruited from callers to the Quitline.Measurements Smoking status and sustained abstinence at 12‐month follow‐up, plus extent of participation in the intervention.Findings Using a conservative analysis (missing data coded as a treatment failure), 6‐month sustained abstinence was reported by significantly more participants in the computer‐generated tailored advice (20%) than the standard printed materials condition (12%) at 12‐month follow‐up OR 1.82 (1.31–2.55)). Group differences in point prevalence abstinence (28% intervention, 25% control) were not significant. Among participants in the tailored advice condition, 6‐month sustained abstinence was associated with the number of advice letters received.Conclusion The provision of a series of tailored, computer‐generated advice letters resulted in greater rates of sustained cessation than for controls. A dose–response relationship was found, with increased compliance with the intervention associated with improved cessation outcomes. The programme appears to have much of its effect by preventing relapse.