The production of Greek-style natural black table olives remains an empirical process relying on spontaneous fermentation despite its economic significance. For this reason producers often resort to increased NaCl concentration of the brine to secure quality of the product. In this study we employ two lactic acid bacteria Leuconostoc mesenteroides subsp. mesenteroides 139 and Lactobacillus pentosus DSM 16366 as starters in separate laboratory low salinity fermentations of “Kalamon” cultivar olives, processed according to the Greek-style method. L. mesenteroides subsp. mesenteroides 139 was previously isolated from Kalamon olives laboratory spontaneous fermentations, while L. pentosus DSM 16366 was isolated from fermenting green olives prepared according to the Spanish-style method. Spontaneous olives fermentation was also performed as a control. Microbiological and physicochemical analyses of the brines revealed that the use of the starters had a significant effect on the olives fermentation, leading to a faster acidification due to the more efficient consumption of soluble sugars in the brines. The final pH value reached by each starter culture used indicates a successful lactic fermentation. The production of lactic acid by the starters and the concomitant drop of the pH value proved to inhibit enterobacteria in a shorter period of time compared to the spontaneous fermentation. Concluding, the use of either of the two lactic acid bacteria as starters in Greek-style Kalamon olives fermentation could lead to a more controllable fermentation at lower salinities. The resulting product could be of higher quality with extended shelf-life while being at the same time safer for the consumer.