The performance of two potential probiotic Lactobacillus strains from olive microbiota, namely L. pentosus B281 and L. plantarum B282 was assessed as starter cultures in Spanish-style fermentation of heat shocked green olives cv. Halkidiki. Two different initial salt levels were studied, 10% (w/v) and 8% (w/v) NaCl, and the brines were inoculated with (a) L. pentosus B281, (b) L. plantarum B282, and (c) a mixture of both strains. A spontaneous fermentation was also taken into account as control treatment. Prior to brining, olives were heat shocked at 80 ?C for 10 min to reduce the level of the indigenous microbiota on olive drupes and facilitate the dominance of the inoculated cultures. Microbiological, physicochemical and sensory analyses were conducted throughout fermentation. The composition of LAB population and the evolution of added inocula were assessed by Pulsed Field Gel Electrophoresis (PFGE). The final population of LAB was maintained above 6 log cycles in olive flesh. Both L. pentosus B281 and L. plantarum B282 were able to dominate over indigenous LAB, albeit strain B281 exhibited higher recovery percentages (100 or 94.7% for B281 and 58.8% or 55.0% for B282 in 10% or 8% NaCl, respectively). L. pentosus B281 also dominated over L. plantarum B282, when the two strains were co-inoculated in olive fermentations. The sensory assessment showed higher preference for inoculated fermentations of L. pentosus and L. plantarum separately in 8% NaCl, followed by the L. plantarum in 10% NaCl. The present study showed that probiotic strains L. pentosus B281 and L. plantarum B282, may offer a great potential for use as functional starter cultures in olive fermentation and deliver a promising probiotic food to the consumer.