This study evaluates the extent to which an intervention (Working Inside for Smoking Elimination [WISE]), based on motivational interviewing and cognitive behavior, decreases relapse to smoking after being released from a smoke-free prison. A total of 262 inmates who smoked prior to incarceration were recruited approximately 8 weeks before their release. Participants were randomized to 6 weekly sessions of either education videos (control) or the WISE intervention. At the 3-week follow-up, 25% of the WISE intervention and 7% of the control participants continued to be tobacco abstinent (odds ratio, 4.4; 95% CI, 2.0-9.7). In the logistic regression analysis, participants randomized to the WISE intervention were 6.6 (95% CI, 2.5-17.0) times more likely to remain tobacco abstinent at the 3-week follow-up than those randomized to the control condition.