Changes in DNA methylation may be a potential mechanism that mediates the effects of smoking on physiological function and subsequent disease risk. Given the dynamic nature of the epigenome, longitudinal studies are indispensable for investigating smoking-induced methylation changes over time. Using blood samples collected approximately five years apart in 380 African Americans (mean age 60.7 years) from the Genetic Epidemiology Network of Arteriopathy (GENOA) study, we measured DNA methylation levels using Illumina HumanMethylation BeadChips. We evaluated the association between Phase 1 smoking status and rate of methylation change, using generalized estimating equation models. Among the 6958 CpG sites examined, smoking status was associated with methylation change for 22 CpGs (false discovery rate q < 0.1), with the majority (91%) becoming less methylated over time. Methylation change was greater in ever smokers than never smokers, and the absolute differences in rates of change ranged from 0.18 to 0.77 per decade in M value, equivalent to a β value change of 0.013 to 0.047 per decade. Significant enrichment was observed for CpG islands, enhancers, and DNAse hypersensitivity sites (p < 0.05). Although biological pathway analyses were not significant, most of the 22 CpGs were within genes known to be associated with cardiovascular disease, cancers, and aging. In conclusion, we identified epigenetic signatures for cigarette smoking that may have been missed in cross-sectional analyses, providing insight into the epigenetic effect of smoking and highlighting the importance of longitudinal analysis in understanding the dynamic human epigenome.