We compared the odds of smoking cessation at 2-months post-myocardial infarction (MI), before and after implementing routines optimizing use of evidence-based smoking cessation methods, with start during admission. The following routines were implemented at six Swedish hospitals: cardiac rehabilitation nurses offering smokers consultation during admission, optimizing nicotine replacement therapy and varenicline prescription, and contacting patients by telephone during the 1st week post-discharge. Using logistic regression, odds for smoking cessation at 2-months before (n smokers/n admitted = 188/601) and after (n = 195/632) routine implementation were compared. Secondary outcomes included adherence to implemented routines and assessing the prognostic value of each routine on smoking cessation. After implementation, a larger proportion of smokers (65% vs. 54%) were abstinent at 2-months (OR 1.60 [1.04–2.48]). Including only those counselled during admission (n = 98), 74% were abstinent (2.50 [1.42–4.41]). After implementation, patients were more often counselled during admission (50% vs. 6%, p < 0.001), prescribed varenicline (23% vs. 7%, p < 0.001), and contacted by telephone post-discharge (18% vs. 2%, p < 0.001). Being contacted by telephone post-discharge (adjusted OR 2.74 [1.02–7.35]) and prescribed varenicline (adjusted OR 0.39 [0.19–0.83]) predicted smoking cessation at 2-months. In conclusion, readily available methods for aiding smoking cessation can be implemented effectively in routine practice, with beneficial effects for post-MI patients.