Six deep-sea proteolytic bacteria taken from Aleutian margin sediments were screened; one of them produced a cold-adapted neutral halophilic protease. These bacteria belong to Pseudoalteromonas spp., which were identified by the 16S rDNA sequence. Of the six proteases produced, two were neutral cold-adapted proteases that showed their optimal activity at pH 7-8 and at temperature close to 35 degrees C, and the other four were alkaline proteases that showed their optimal activity at pH 9 and at temperature of 40-45 degrees C. The neutral cold-adapted protease E1 showed its optimal activity at a sodium chloride concentration of 2 M, whereas the activity of the other five proteases decreased at elevated sodium chloride concentrations. Protease E1 was purified to electrophoretic homogeneity and its molecular mass was 34 kDa, as estimated by sodium dodecyl sulfate-polyacrylamide gel electrophoresis (SDS-PAGE). The molecular weight of protease E1 was determined to be 32,411 Da by mass spectrometric analysis. Phenylmethyl sulfonylfluoride (PMSF) did not inhibit the activity of this protease, whereas it was partially inhibited by ethylenediaminetetra-acetic acid sodium salt (EDTA-Na). De novo amino acid sequencing proved protease E1 to be a novel protein.