Selected Bacillus and Enterococcus strains, isolated from traditional okpehe fermentations, were studied for their suitability as starter cultures in laboratory-scale fermentations of Prosopis africana seeds for the production of okpehe, a traditional fermented vegetable product of Nigeria. The strains were selected on the basis of highest proteolytic activity, as determined with the APIZYM (BioMerieux) test. The choice of starter strains was narrowed to Bacillus subtilis strains BFE 5301 and BFE 5372. These were determined as the best starter combination because of rapid growth, high amylolytic and proteolytic activities, high levels of polyglutamic acid production by strain BFE 5372, as well as bacteriocin production by strain BFE 5301. Other mixed culture fermentations did not yield sensorically acceptable products. Although a monoculture fermentation, using only B. subtilis strain BFE 5372, produced okpehe with very good sensory characteristics, the growth of B. cereus could be detected after 48 h fermentation, indicating that this starter did not sufficiently contribute to product safety. Mixed culture fermentation with the combination of bacteriocin-producing starter B. subtilis BFE 5301 and the non-bacteriocin-producing B. subtilis BFE 5372, produced a product with good sensory characteristics, in which growth of B. cereus was delayed. The bacteriocin produced by B. subtilis strain BFE 5301 was identified as subtilisin, using subtilisin-specific primers and PCR amplification of the subtilisin gene. The bacteriocin was heat-stable at 100 degrees C for 10 min and exhibited highest activity at pH values lower or equal to pH 6.0. The bacteriocin was sensitive to the proteolytic enzymes trypsin and alpha-chymotrypsin at concentrations of 10 mg/ml.