We used eight informative microsatellite markers for fingerprinting and evaluation of genetic similarity among 15 Tunisian olive (Olea europaea L.) cultivars and two feral unknown trees named Soulela 1 and Soulela 2. Thirty-one alleles were revealed, and the number of alleles per SSR varied from 2 (UDO12) to 6 (GAPU71A). Cluster analysis grouped cultivars into three main clusters. The two unknown varieties could not be reliably classified into any of these cultivar groups. SSR analysis indicated the presence of three erroneous denominations of cultivars. We resolved two synonymy cases (Zalmati and Chemlali; Rkhami and Chetoui) and one case of homonymy (Chemlali Tataouine). Genetic analyses of DNA extracted from leaves, oils, and embryos of the two unknown cultivars and the two major Tunisian olive cultivars (Chemlali and Chetoui) were also studied. We conclude that the reliable identification of these two feral cultivars needs to be addressed by a larger set of markers.