A high yield cellulase production strain was screened from the surface of cigar wrapper leaves and added to cigar wrapper leaves for fermentation in the present study. The enzyme-producing strain was identified as Bacillus velezensis, and its maximum carboxymethyl cellulase activity could reach 44.3 U/mL. Making the cellulose degradation rate of cigar wrapper leaves as the index, the fermentation temperature, inoculum concentration, and carbon and nitrogen source addition concentration were optimized by response surface methodology. The results showed that under the conditions of inoculation concentration of 20%, fermentation temperature of 37 °C, addition of 4.5 ‰ glucose and 2.25 ‰ glutamate, the highest degradation rate of tobacco cellulose was 31.7%. Significance analysis results showed that the order of factors affecting the degradation rate of cigar wrapper cellulose was: inoculation concentration > carbon and nitrogen source addition concentration > temperature. The analysis of aroma substances under the optimal conditions found that the total amount of aroma substances of cigar wrapper increased by 26.1% compared with that before fermentation, in which β-damascenone, megastigmatrienone, farnesyl acetone, and solanone were significantly improved. The results were conducive to improving the aroma quality and concentration of cigar wrapper leaves.