We evaluated associations of smoking heaviness markers and the effects of smoking cessation on the intestinal microbiota and cardiovascular disease risk factors in current smokers undertaking a quit attempt. Participants were current smokers enrolled in a prospective randomized clinical trial of smoking cessation therapies with visits at baseline, 2, and 12 weeks. Genomic DNA was extracted from fecal samples followed by 16S rRNA gene sequencing and analysis using the QIIME2 software workflow. Relative abundances of bacterial taxa and alpha- and beta-diversity measures were used for comparisons. The 36 smokers were (mean (standard deviation)) 51.5 (11.1) years old (42% male) and smoked 15.1 (6.4) cigarettes per day for 22.7 (11.9) pack-years. Relative abundances of the phylum Actinobacteria correlated with pack-years (rho = −0.44, p = 0.008) and Cyanobacteria correlated with CO levels (rho = 0.39, p = 0.021). After 12 weeks, relative abundances of the phylum Bacteroidetes increased (pANCOVA = 0.048) and Firmicutes decreased (pANCOVA = 0.036) among abstainers compared to continuing smokers. Increases in alpha-diversity were associated with heart rates (rho = −0.59, p = 0.037), systolic blood pressures (rho = −0.58, p = 0.043), and C-reactive protein (rho = −0.60, p = 0.034). Smoking cessation led to minor changes in the intestinal microbiota. It is unclear if the proven health benefits of smoking cessation lead to salutary changes in the intestinal microbiota.