The aim of this study was to isolate, screen and optimize proteolytic bacteria from different soil samples. Soil samples collected from El-Sharkia Governorate and Wadi Abu Sobeira, Aswan Governorate were screened for proteolytic bacteria. The later soil was characterized by saline soil. Proteolytic bacteria from each soil was studied by cultivating in a protease production medium (PPM), low in carbon content. Substrate specificity of the isolated proteolytic bacteria was assayed by adding seven nitrogen sources and six carbon sources. Each one was added to PPM compared to the control (peptone and glucose), respectively. Four bacterial isolates were selected and they exhibited excellent ability to hydrolyze high-molecular weight proteins (skim milk, gelatin and casein). These isolates showed extracellular protease activity on skim milk agar plates (20 mm) after 24 hr., at 37^◦C. These isolates were identified as Bacillus cereus strain A1(4), B. toyonensis A3(14), B. cereus strain A4(26) and B. cereus strain A8(60) based on partial sequencing of 16S rDNA. Protease production by these strains [A1 (4), A3 (14), A4 (26) and A8(60)] compared to B. subtilis cultivate in PPM reached a maximum at 24 and 48 hr., with values ranged between 81.83 and 76.16 U/ml. Starch and mannitol were the best substrates for enzyme production, while glycerol could not influence production of protease. Among various organic nitrogen sources, beef extract, soybean and skim milk, which are, commercial, were found as the best substrate for bacterial growth and enzyme production, while NaNO₃, KNO₃ and (NH4)₂SO₄ could not affect production of protease or bacterial growth. This enzyme showed high capability for removing proteins and stain spots from cloths.