Several studies have recently identified strong epigenetic signals related to tobacco smoking. However, an aspect that did not receive much attention is the evolution of epigenetic changes with time since smoking cessation. We conducted a series of epigenome-wide association studies to capture the dynamics of smoking-induced epigenetic changes after smoking cessation, using genome-wide methylation profiles obtained from blood samples in 745 women from 2 European populations. Two distinct classes of CpG sites were identified: sites whose methylation reverts to levels typical of never smokers within decades after smoking cessation, and sites remaining differentially methylated, even more than 35 years after smoking cessation. Our results suggest that the dynamics of methylation changes following smoking cessation are driven by a differential and site-specific magnitude of the smoking-induced alterations (with persistent sites being most affected) irrespective of the intensity and duration of smoking. Analyses of the link between methylation and expression levels revealed that methylation predominantly and remotely down-regulates gene expression. Among genes whose expression was associated with our candidate CpG sites, LRRN3 appeared to be particularly interesting as it was one of the few genes whose methylation and expression were directly associated, and the only gene in which both methylation and gene expression were found associated with smoking. Our study highlights persistent epigenetic markers of smoking, which can potentially be detected decades after cessation. Such historical signatures are promising biomarkers to refine individual risk profiling of smoking-induced chronic disease such as lung cancer.