The article reviews the available information on the start of fruit tree cultivation in the Old World. On the basis of (i) evaluation of the available archeological remains and (ii) examination of the wild relatives of the cultivated crops, it was concluded that olive, grape, date, and fig were the first important horticultural additions to the Mediterranean grain agriculture. They were most likely domesticated in the Near East in protohistoric time (fourth and third millennia B.C.) and they emerge as important food elements in the early Bronze Age. Domestication of all four fruit trees was based on a shift from sexual reproduction (in the wild) to vegetative propagation of clones (under domestication). Olive, grape, date, and fig can be vegetatively propagated by simple techniques (cuttings, basal knobs, suckers) and were thus preadapted for domestication early in the development of agriculture. The shift to clonal propagation placed serious limitations on selection and on fruit set under cultivation. We have examined the consequences of this shift in terms of the genetic makeup of the cultivars and traced the various countermeasures that evolved to ensure fruit set. Finally, it was pointed out that in each of these classic fruit trees we are confronted with a variable complex of genuinely wild types, secondary weedy derivatives and feral plants, and groups of the domesticated clones, which are all interfertile and interconnected by occasional hybridization. It was concluded that introgression from the diversified wild gene pool facilitated the rapid buildup of variation in the domesticated crops.