The physiologic response to tobacco smoke can be measured by gene-expression profiling of the airway epithelium. Temporal resolution of kinetics of gene-expression alterations upon smoking-cessation might delineate distinct biological processes that are activated during recovery from tobacco smoke exposure. Using whole genome gene-expression profiling of individuals initiating a smoking-cessation attempt, we sought to characterize the kinetics of gene-expression alterations in response to short-term smoking-cessation in the nasal epithelium. RNA was extracted from the nasal epithelial of active smokers at baseline and at 4, 8, 16, and 24-weeks after smoking-cessation and put onto Gene ST arrays. Gene-expression levels of 119 genes were associated with smoking-cessation (FDR < 0.05, FC ≥1.7) with a majority of the changes occurring by 8-weeks and a subset changing by 4-weeks. Genes down-regulated by 4- and 8-weeks post-smoking-cessation were involved in xenobiotic metabolism and anti-apoptotic functions respectively. These genes were enriched among genes previously found to be induced in smokers and following short-term in vitro exposure of airway epithelial cells to cigarette smoke (FDR < 0.05). Our findings suggest that the nasal epithelium can serve as a minimally-invasive tool to measure the reversible impact of smoking and broadly, may serve to assess the physiological impact of changes in smoking behavior.