The probiotic characteristics of Lactobacillus brevis BG18 and Lb. plantarum BG33, isolated from traditional Turkish Tulum cheese were assessed. These two bacteriocinproducer strains exhibited good probiotic characteristics such as resistance in media containing 0.3% bile salt, pepsin (3 mg mL(-1)), and pancreatine (1 mg mL(-1)) as well as acid resistance at pH 2. They were also adhered to Caco-2 epithelial cells in a manner comparable to Escherichia coli LMG3083 (ETEC) and Salmonella Typhimurium SL1344. The strains produced a heat-stable antimicrobial compound that was shown to be proteinaceous in nature, and therefore, referred to as bacteriocins. The bacteriocins were able to inhibit growth of a number gram-positive bacteria such as Listeria monocytogenes, Clostridium botulinum, Staphylococcus aureus and Bacillus cereus. Tricine-SDS-PAGE of the active fraction resulted in single bands with estimated molecular masses of 2.5 kDA and 2.7 kDA for Lb. brevis BG18 and Lb. plantarum BG33 bacteriocins, respectively.