Agricultural activities, including practices, crops and techniques have evolved throughout history undergoing tremendous changes. From the early Neolithic farmers in the Mediterranean focused on cereal agriculture and only later, during the 4th/3rd millennium cal. BC in the Eastern basin, other species such as fruit trees were introduced into the agrarian system transforming the model that had been in use for millennia. Fruit tree management required innovation and investment and more importantly multi-year foresight as the new crops entailed a new pace of work with delayed returns and, thus, a greater entanglement with the land. Processes of social complexity and urbanization accompanied the emergence of arboriculture which occurred at different pace at both ends of the Mediterranean. This paper focuses on the Iberian Peninsula, the most western Mediterranean region, during the 1st millennium cal. BC when arboriculture spread after commercial encounters with oriental seafarers. Here we report the earliest archaeobotanical evidence (seeds and fruits) for the introduction of fruit cultivation in Iberia. Results from several sites indicate that the spread of fruit cultivation was a long process that varied regionally. In some areas the new crops were rapidly adopted and integrated into the Mediterranean trading networks while in other regions arboriculture was not developed until the end of the millennium. Of the various fruit products that were commercialized, wine occupied a most relevant role.