Even though Cyprus was an important crossing point for the westward spread of olive, and one of the primary regions of domestication, its genetic recourses remain uncharted at a great extent. Throughout the centuries, a number of ancient olive trees remain in the same orchards, contributing to Cypriot oleiculture and society. In an attempt to explore this monumental genetic pool, a survey was conducted to identify centennial olive trees in rural provinces of Cyprus. Microsatellites were employed in order to study their genetic composition (including rootstocks when feasible) and to establish possible associations among genotypes. High numbers of specific alleles, suggestive of the distinctiveness of this germplasm, were detected, and both grafting and rootstock propagation was verified. Moreover, it was determined by Bayesian structural and network reticulate analysis that centennial olives can be divided in two discrete genetic clusters having intermediate admixed accessions. Furthermore, it was determined that all contemporary Cypriot cultivars, that were included in the present study, were highly affiliated exclusively to one genetic group, a strong evidence of selection among elite clones. The information acquired from the current study reveals the genetic rareness of this material and its contribution to the current olive germplasm.