Data on the dose-dependent effects of smoking and smoking cessation on tooth loss are scarce. We hypothesized that smoking has both dose- and time-dependent effects on tooth loss incidence. We used longitudinal data on tobacco use and incident tooth loss in 43,112 male health professionals, between 1986 and 2002. In multivariate Cox models, current smokers of 5 to 14 and 45+ cigarettes daily had a two-fold (HR, 1.94; 95% CI, 1.72, 2.18) and three-fold (HR, 3.05; 95% CI, 2.38, 3.90) higher risk of tooth loss, respectively, compared with never-smokers. Risk decreased with increasing time since cessation, but remained elevated by 20% (95% CI, 16%, 25%) for men who had quit 10+ years before. Current pipe/cigar smokers had a 20% (95% CI, 1.11, 1.30) increased risk of tooth loss compared with never- and former smokers of pipes/cigars.