It has been demonstrated that smoking cessation alters the subgingival microbial profile; however, the response of individual bacteria within this ecosystem has not been well studied. The aim of this investigation, therefore, was to longitudinally examine the effect of smoking cessation on the prevalence and levels of selected subgingival bacteria using molecular approaches for bacterial identification and enumeration. Subgingival plaque was collected from 22 smokers at the baseline and 12 months following periodontal nonsurgical management and smoking cessation counseling. The prevalence and abundance of selected organisms were examined using nested PCR and multiplexed bead-based flow cytometry. Eleven subjects successfully quit smoking over 12 months (quitters), while 11 continued to smoke throughout (smokers). Smoking cessation led to a decrease in the prevalence of Porphyromonas endodontalis and Dialister pneumosintes at 12 months and in the levels of Parvimonas micra, Filifactor alocis, and Treponema denticola. Smoking cessation also led to an increase in the levels of Veillonella parvula. Following nonsurgical periodontal therapy and smoking cessation, the subgingival microbiome is recolonized by a greater number of health-associated species and there are a significantly lower prevalence and abundance of putative periodontal pathogens. The results indicate a critical role for smoking cessation counseling in periodontal therapy for smokers in order to effectively alter the subgingival microbiome.