The purpose of this study was to characterize and compare subgingival microbiome before and after periodontal treatment to learn if any changes of the subgingival microbiome were reflected in intra-oral halitosis. We tested the hypothesis that intra-oral halitosis (Volatile sulfur compounds levels) correlates with corresponding subgingival bacterial levels before and after periodontal treatment. Twenty patients with generalized periodontitis completed the study. Subgingival plaque samples were collected at baseline and 6–8 weeks after nonsurgical periodontal therapy. Full-mouth periodontal status assessed probing depth (PD), clinical attachment loss (CAL), gingival recession (REC), bleeding on probing (BoP), PISA and PESA. Halitosis assessment was made using a volatile sulfur compounds (VSC) detector device. Periodontal measures were regressed across VSC values using adjusted multivariate linear analysis. The subgingival microbiome was characterized by sequencing on an Illumina platform. From a sample of 20 patients referred to periodontal treatment, 70% were females (n = 14), with a mean age of 56.6 (±10.3) years; full-mouth records of PD, CAL, BOP (%) allowed to classify the stage and grade of periodontitis, with 45% (n = 9) of the sample having Periodontitis Stage IV grade C and 95% (n = 19) had generalized periodontitis. The correlation of bacterial variation with VSCs measured in the periodontal diagnosis and in the reassessment after treatment were evaluated. Fusobacterium nucleatum, Capnocytophaga gingivalis and Campylobacter showaei showed correlation with the reduction of VSC after periodontal treatment (p-value = 0.044; 0.047 and 0.004, respectively). Capnocytophaga sputigena had a significant reverse correlation between VSCs variation from diagnosis (baseline) and after treatment. Microbial diversity was high in the subgingival plaque on periodontitis and intra-oral halitosis participants of the study. Furthermore, there were correlations between subgingival plaque composition and VSC counting after periodontal treatment. The subgingival microbiome can offer important clues in the investigation of the pathogenesis and treatment of halitosis.