In order to degrade protein of tobacco and improve the smoking quality of tobacco, 18 protein degrading bacterias from flue-cured tobacco of Henan, Fujian, Yunnan province were isolated through protein degrading selective medium. The activity of protease was detected, and the strain with highest protease-producing was identified by the 16S rRNA gene sequence and physiological-biochemical tests. Orthogonal experiment was further designed to get the optimal fermentation conditions of protein degrading in the tobacco leaf. And then the sensory quality of tobacco leaves after treatment was investigated The results showed that: (1) Strain HN-3 was the preferred strain with the highest activity of protease enzyme producing (3 417 U/mL). (2) Strain HN-3 was identified as Bacillus pumilus by the 16S rRNA gene sequence and physiological-biochemical tests. (3) The orthogonal experiment results suggested that, by adding 3% culture medium (with strain HN-3) to the surface of tobacco leaf, the degrading rates of protein could reach 29.66% after 84 hours fermentation under the 37 ℃. (4) The sensory evaluation results showed that after fermentation, the aroma of tobacco leaves was changed well. The amount of aroma and smoke increased, while the gas content decreased, the aftertaste improved, and the overall sensory quality of tobacco was improved obviously.