Smoking has been identified in observational studies as a risk factor for bacterial vaginosis (BV), a condition defined in part by decimation of Lactobacillus spp. The anti-estrogenic effect of smoking and trace amounts of benzo[a]pyrene diol epoxide (BPDE) may predispose women to BV. BPDE increases bacteriophage induction in Lactobacillus spp. and is found in the vaginal secretions of smokers. We compared the vaginal microbiota between smokers and non-smokers and followed microbiota changes in a smoking cessation pilot study. In 2010–2011, 20 smokers and 20 non-smokers were recruited to a cross-sectional study (Phase A) and 9 smokers were enrolled and followed for a 12-week smoking cessation program (Phase B). Phase B included weekly behavioral counseling and nicotine patches to encourage smoking cessation. In both phases, participants self-collected mid-vaginal swabs (daily, Phase B) and completed behavioral surveys. Vaginal bacterial composition was characterized by pyrosequencing of barcoded 16S rRNA genes (V1-V3 regions). Vaginal smears were assigned Nugent Gram stain scores. Smoking status was evaluated (weekly, Phase B) using the semi-quantitative NicAlert® saliva cotinine test and carbon monoxide (CO) exhalation. In phase A, there was a significant trend for increasing saliva cotinine and CO exhalation with elevated Nugent scores (P value <0.005). Vaginal microbiota clustered into three community state types (CSTs); two dominated by Lactobacillus (L. iners, L. crispatus), and one lacking significant numbers of Lactobacillus spp. and characterized by anaerobes (termed CST-IV). Women who were observed in the low-Lactobacillus CST-IV state were 25-fold more likely to be smokers than those dominated by L. crispatus (aOR: 25.61, 95 % CI: 1.03-636.61). Four women completed Phase B. One of three who entered smoking cessation with high Nugent scores demonstrated a switch from CST-IV to a L.iners-dominated profile with a concomitant drop in Nugent scores which coincided with completion of nicotine patches. The other two women fluctuated between CST-IV and L. iners-dominated CSTs. The fourth woman had low Nugent scores with L. crispatus-dominated CSTs throughout. Smokers had a lower proportion of vaginal Lactobacillus spp. compared to non-smokers. Smoking cessation should be investigated as an adjunct to reducing recurrent BV. Larger studies are needed to confirm these findings.