We aimed to explore the association between volatile sulfurous compounds (VSCs) and periodontal epithelial surface area (PESA) and periodontal inflamed surface area (PISA) on a cohort of periodontitis patients. Consecutive patients were assessed for periodontitis and halitosis. A full-mouth periodontal status assessment tested probing depth (PD), clinical attachment loss (CAL), gingival recession (REC), bleeding on probing (BoP), PISA and PESA. A halitosis assessment was made using a VSC detector device. Periodontal measures were regressed across VSC values using adjusted multivariate linear analysis. From a total of seventy-two patients (37 females/35 males), the PESA of posterior-lower regions was found to be significantly higher in halitosis cases than their non-halitosis counterparts (p = 0.031). Considering all patients, the PESA of the posterior-lower region (B = 1.3, 95% CI: 0.2–2.3, p = 0.026) and age (B = −1.6, 95% CI: −3.1–0.2, p = 0.026) showed significant association with VSCs. In halitosis patients, the PESA of the posterior-lower region (B = 0.1, 95% CI: 0.0–0.1, p = 0.001), PISA Total (B = −0.1, 95% CI: −0.1–0.0, p = 0.008) and the OHIP-14 domain of physical disability (B = −2.1, 95% CI:−4.1–0.1, p = 0.040) were the most significant variables in this model. The PESA from the posterior-lower region may be associated with VSCs when other causes of extra-oral halitosis are excluded. Further intervention studies are needed to confirm this association.