The aim of this study was to investigate the association between cigarette smoking and smoking cessation and the prevalence and incidence of tooth loss in a large cohort study in Germany. We analyzed data of 23,376 participants of the European Prospective Investigation into Cancer and Nutrition (EPIC)–Potsdam study recruited between 1994 and 1998 from the general population in Potsdam and other parts of Brandenburg, Germany, who had complete data on cigarette smoking, tooth loss, and covariates. Negative binomial regression and tooth-specific logistic regression models were fit to evaluate the association between smoking and the baseline prevalence and incidence of tooth loss during follow-up, respectively. Cigarette smoking was associated with higher prevalence of tooth loss at baseline as well as higher incidence of tooth loss during follow-up. The association between smoking and the incidence of tooth loss was stronger in men than women and stronger in younger versus older individuals. Heavy smoking (≥15 cigarettes/d) was associated with >3 times higher risk of tooth loss in men (odds ratio, 3.6; 95% confidence interval, 3.0, 4.4) and more than twice the risk of tooth loss in women (odds ratio, 2.5; 95% confidence interval, 2.1, 2.9) younger than 50 y when compared with never smokers. Smoking cessation was consistently associated with a reduction in tooth loss risk, with the risk of tooth loss approaching that of never smokers after approximately 10 to 20 y of cessation.