In recent years, several studies have shown that the levels of volatile sulfur compounds are higher in periodontitis patients. However, the relationship between periodontal disease and bad breath is still controversial. Aspects that should be clarified include its relation to periodontitis severity, the influence of risk variables and the subject of the present research, that is treatment choice. To help clinicians and patients when deciding about mechanical periodontal therapy, 30 patients with advanced chronic periodontitis were selected from the periodontics clinic, Dental School, Pontiphical Catholic University of Minas Gerais from April 2013 to May 2014. A complete periodontal clinical examination was performed and the following parameters were recorded: probing depth (PD), clinical attachment level (CAL), bleeding on probing, plaque index, and tongue coating index. Halitosis was assessed by using the organoleptic method and measurements of volatile sulfur compounds (VSC), including hydrogen sulfide (H2S) and methyl mercaptan (CH3SH) by using gas chromatography, at baseline and 90 days after non-surgical periodontal treatment. After periodontal clinical examination, individuals were randomly allocated to full-mouth scaling (FMS) - completed within 24 hours - or to conventional quadrant-wise scaling and root planing (SRP) - completed within 2 months. Halitosis and sulfur gas levels were were statistically compared (Mann-Whitney and Wilcoxon tests, p < 0.05). For inter- and intra-group comparisons regarding categorical variables Chi-square, McNemar, and Fisher exact tests were used. Primary outcome was halitosis changing.