Background Alkaline proteases are among the most important classes of industrial hydrolytic enzymes. The industrial demand for alkaline proteases with favorable properties continues to enhance the search for new enzymes. The present study focused on isolation of new alkaline producing alkaliphilic bacteria from hyper saline soda lakes and optimization of the enzyme production. Results A new potent alkaline protease producing halotolerant alkaliphilic isolate NPST-AK15 was isolated from hyper saline soda lakes, which affiliated to Bacillus sp. based on 16S rRNA gene analysis. Organic nitrogen supported enzyme production showing maximum yield using yeast extract, and as a carbon source, fructose gave maximum protease production. NPST-AK15 can grow over a broad range of NaCl concentrations (0-20%), showing maximal growth and enzyme production at 0-5%, indicated the halotolerant nature of this bacterium. Ba and Ca enhanced enzyme production by 1.6 and 1.3 fold respectively. The optimum temperature and pH for both enzyme production and cell growth were at 40°C and pH 11, respectively. Alkaline protease secretion was coherent with the growth pattern, started at beginning of the exponential phase and reached maximal in mid stationary phase (36 h). Conclusions A new halotolerant alkaliphilic alkaline protease producing Bacillus sp. NPST-AK15 was isolated from soda lakes. Optimization of various fermentation parameters resulted in an increase of enzyme yield by 22.8 fold, indicating the significance of optimization of the fermentation parameters to obtain commercial yield of the enzyme. NPST-AK15 and its extracellular alkaline protease with salt tolerance signify their potential applicability in the laundry industry and other applications.