Knowledge on the structure and distribution of genetic diversity is a key aspect in order to plan and execute an efficient conservation and utilization of the genetic resources of any crop as well as for determining historical demographic inferences. In this work, a large data set of 1765 accessions of cherimoya (Annona cherimola Mill, Annonaceae), an underutilized fruit tree crop native to the neotropics and used as a food source by pre-Columbian cultures, was collected from 6 different countries across the American continent and amplified with 9 highly informative microsatellite markers. The structure analyses, fine representation of the genetic diversity and an ABC approach suggest a Mesoamerican origin of the crop, contrary to previous reports, with clear implications for the dispersion of plant germplasm between Central and South America in pre-Columbian times. These results together with the potential distribution of the species in a climatic change context using two different climate models provide new insights for the history and conservation of extant genetic resources of cherimoya that can be applied to other currently underutilized woody perennial crops.