Traceability and authenticity of olive oils have become a major instrument to guarantee the consumer’s protection. Recently, determination of adulteration of olive oils is based on the analysis of simple sequence repeats. In this study, we evaluate the feasibility of identifying above cultivars and the derived oils by the analysis of SSR markers. To this purpose, 22 virgin olive oils were prepared in the laboratory and DNA was extracted using a commercial kit, and 8 SSR markers were analyzed. The obtained results indicated that the comparison of the genetic profile of DNA extracted from oil and leaves of the cultivars studied concluded different genetic profiles in some cultivars when studied for their genome as well as for their oils. These additional alleles in oil’s profile appear as minor peaks can be originating from the pollinators and which are present in the genome of the seed embryo. Hierarchical classification of varieties based on similarity measures and clustering was globally inconsistent with the grouping of varieties by end use and the geographical origin. Finally, we set up a categorization means to discriminate all the types of oil among them with the minimum of markers (three markers).