A new Bacillus strain degrading starch, named Bacillus sp. UEB-S, was isolated from a southern Tunisian area. Amylase production using solid-state fermentation on millet, an inexpensive and available agro-resource, was investigated. Response surface methodology was applied to establish the relationship between enzyme production and four variables: inoculum size, moisture-to-millet ratio, temperature, and fermentation duration. The maximum enzyme activity recovered was 680 U/g of dry substrate when using 1.38 × 109 CFU/g as inoculation level, 5.6:1 (ml/g) as moisture ratio (86%), for 4 days of cultivation at 37oC, which was in perfect agreement with the predicted model value. Amylase was purified by Q-Sepharose anion-exchange and Sephacryl S-200 gel filtration chromatography with a 14-fold increase in specific activity. Its molecular mass was estimated at 130 kDa. The enzyme showed maximal activity at pH 5 and 70oC, and efficiently hydrolyzed starch to yield glucose and maltose as end products. The enzyme proved its efficiency for digesting raw cereal below gelatinization temperature and, hence, its potentiality to be used in industrial processes.