Unidentified olive plants naturally grow in the Golestan province of Iran, on different soils and under climates spanning from sub-temperate to desert conditions, represented by single trees or groups of few trees. We collected samples from representative sites and analyzed them by simple sequence repeat markers in order to determine their identity and their relationships to prominent Iranian and Mediterranean reference cultivars. Population structure analysis separated these ecotypes from Mediterranean and, surprisingly, from all Iranian cultivars, the parentage test excluded their direct contribution as candidate parents or offspring of cultivars, and they also showed a high level of admixture. Their differentiation from cultivated olives may be attributed to different factors: they could represent wild plants or could derive from natural dissemination of ancestral cultivated trees. Their survival up to now may be due to the fact that most of them are grown on sacred sites such as necropolis. Anyhow, the adaptation to strong environmental stresses, and their fruit size and oil content make the olive Golestan ecotypes a valuable source of genetic variation previously uncharacterized and currently threatened with extinction.