Abstract: To screen for Bacillus strains with excellent fermentation performance to improve the quality of cigar tobacco leaves, volatile components in the fermentation broths of different strains and in fermented cigar tobacco powder were analyzed using headspace solid-phase microextraction–gas chromatography–mass spectrometry (HS-SPME-GC-MS) and electronic nose technology, based on 16S rDNA sequence analysis and olfactory evaluation of the fermentation broths. Multivariate analysis was then used to select superior aroma-producing strains, and simulated fermentation was conducted to verify their effects on improving the quality of cigar tobacco leaves. The results showed that a total of 50 Bacillus strains were identified, and the odor characteristics of their fermentation broths varied significantly. A total of 177 volatile compounds were detected in the fermentation broths of these strains. The fermentation broths of seven strains exhibited prominent aromatic properties, with 2,3-butanedione, 2-nonanol, and isoamyl alcohol identified as their common aroma components. Principal component analysis and cluster analysis of the fermented tobacco powder led to the selection of two strains, 1-F-2 and DMMJ-4, which showed significant differences in their volatile compound profiles. Strain 1-F-2 significantly increased the relative contents of alcohols, pyrazines, and ketones, whereas strain DMMJ-4 notably increased the relative contents of alcohols, pyridines, and ketones. Fermentation results of the cigar tobacco leaves indicated that these two strains significantly increased the relative contents of volatile components in the leaves, optimized their aroma, smoke, and taste, and improved the overall sensory quality.