Abstract: To screen Bacillus spp. for their excellent fermentation performance to improve the quality of cigar tobacco leaves, volatile components in the fermentation broths of different strains and fermented cigar tobacco powder were analyzed using headspace solid-phase microextraction-gas chromatography-mass spectrometry (HS-SPME-GC-MS) and electronic nose analysis, supplemented by 16S rDNA sequence and olfactory evaluation. Multivariate analysis was employed to select superior aroma-producing strains, and simulated fermentation was conducted to verify their effects to improve the quality of cigar tobacco leaves. The results showed that a total of 50 Bacillus spp. were identified, and the odor characteristics of their fermentation broth varied significantly. A total of 177 volatile components was detected in the fermentation broth of these strains. The fermentation broth 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 component profiles. Strain 1-F-2 significantly increased the relative contents of alcohols, pyrazines, and ketones, and strain DMMJ-4 significantly 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, enhanced their aroma and taste, and improved the overall sensory quality.