As a portable source of food, water, fuel, and construction materials, the coconut (Cocos nucifera L.) played a fundamental role in human migrations and the development of civilization across the humid tropics. Here we investigated the coconut's domestication history and its population genetic structure as it relates to human dispersal patterns. A sample of 1,322 coconut accessions, representing the geographical and phenotypic diversity of the species, was examined using ten microsatellite loci. Bayesian analyses reveal two highly genetically differentiated subpopulations that correspond to the Pacific and Indo-Atlantic oceanic basins. This pattern suggests independent origins of coconut cultivation in these two world regions, with persistent population structure on a global scale despite long-term human cultivation and dispersal. Pacific coconuts show additional genetic substructure corresponding to phenotypic and geographical subgroups; moreover, the traits that are most clearly associated with selection under human cultivation (dwarf habit, self-pollination, and “niu vai” fruit morphology) arose only in the Pacific. Coconuts that show evidence of genetic admixture between the Pacific and Indo-Atlantic groups occur primarily in the southwestern Indian Ocean. This pattern is consistent with human introductions of Pacific coconuts along the ancient Austronesian trade route connecting Madagascar to Southeast Asia. Admixture in coastal east Africa may also reflect later historic Arab trading along the Indian Ocean coastline. We propose two geographical origins of coconut cultivation: island Southeast Asia and southern margins of the Indian subcontinent.