Naturally fermented black table olives of the Gemlik variety are one of the most consumed fermented products in Turkey. The objective of this work was to identify yeast strains isolated during their natural fermentation by using Restriction Fragments Lengths Polymorphism-Polimerase Chain Reaction (RFLP-PCR) and DNA sequencing methods. The study also focused on determining the effect of regional differences on yeast microflora of naturally fermented Gemlik olives. A total of 47 yeast strains belonging to 12 different species which had been previously isolated from the natural brine of Akhisar and Iznik-Gemlik cv. olives were characterized by molecular methods. Forty-two of the tested strains could be identified by RFLP-PCR to species level. These yeast species were determined as Candida mycetangi, Candida hellenica, Candida membranaefaciens, Candida famata, Candida pelliculosa, Saccharomyces cerevisiae, and Zygosaccharomyces mrakii. Five strains were identified by DNA sequencing. These strains belonged to three different species: Aureobasidium pullulans, Kloeckera apiculate, and Cryptococcus saitoi. The most frequent species were C. famata and C. pelliculosa in both regions.