Twenty five haloalkaliphilic bacterial strains were isolated from sea water along the Coastal Gujarat (India) and screened for their ability to secret alkaline proteases. Among them, a potent strain S-20-9 (GenBank accession number EU118360), resembling to Halophilic Bacterium MBIC3303 on the basis of 16S rRNAg ene sequencing, was selected for the optimization of enzyme production. S-20-9 produced protease optimally, under aerobic conditions during mid-stationary phase over a broad range of salt ($5{sim}25%$, w/v) and pH ($7{sim}10$). The optimum production was at pH 9 and 15% (w/v) NaCl. The production was suppressed by lactose, maltose, sucrose, and inorganic nitrogen sources, especially ammonium ions. Further, the production was significantly stimulated by $KH_2PO_4$ and suppressed by glucose. Similarly, the production was also suppressed at higher concentrations of gelatin, yeast extract, peptone, and casamino acids, indicating towards a threshold value for nitrogen requirement. The growth and protease production were enhanced by mono-valent cation (KCl), while the divalent cations acted as inhibitors. The study holds significance as only few reports are available on the alkaline proteases from haloalkaliphilic bacteria, particularly those from moderate saline habitats.