A strain of potential producer of fibrinolytic enzyme was isolated from shrimp Jeot-Gal, a tiny salted shrimps, and identified as Bacillus sp.. The preliminary experiment showed an enzyme yield of 18 U/mL in medium for screening. The carbon, nitrogen and salts significantly influenced the fibrinolytic enzyme production. An optimized medium containing 2% skim milk, 2% soluble starch and 3% NaCl (pH 7.5) after 72 hrs fermentation time at $37^{circ}C$ yielded 3-fold increase in enzyme production, 62 U/mL.