Vanilla is a clonally propagated crop originating from Mesoamerica. Information regarding the circumstances under which vanilla cultivation began is incomplete. Presumably, the Totonac people of Papantla (north-central Veracruz, Mexico) were the earliest to cultivate vanilla; however, the oldest reports of vanilla use relate to the pre-Columbian Maya of southeastern Mexico/Central America, where vanilla was a cacao-beverage spice. We utilized Amplified Fragment Length Polymorphism (AFLP) marker diversity to infer the origins and relationships among cultivated and non-cultivated vanilla in Mesoamerica and on islands in the Indian Ocean, which comprise today's principal production regions of vanilla. Our results suggest that, genetically, vanilla cultivated outside of Mesoamerica is most closely related to cultivated stock from Papantla; whereas unique clones of V. planifolia are found in non-cultivated and cultivated individuals from elsewhere in Mesoamerica. This is consistent with a single origin for cultivated vanilla outside of Mexico, along with multiple origins for cultivated material within Mexico. These data suggest that vestiges of pre-Columbian Maya vanilla cultivars are not found in commercial production today.