The Austronesian settlement of the remote island of Madagascar remains one of the great puzzles of Indo-Pacific prehistory. Although linguistic, ethnographic, and genetic evidence points clearly to a colonization of Madagascar by Austronesian language-speaking people from Island Southeast Asia, decades of archaeological research have failed to locate evidence for a Southeast Asian signature in the island's early material record. Here, we present new archaeobotanical data that show that Southeast Asian settlers brought Asian crops with them when they settled in Africa. These crops provide the first, to our knowledge, reliable archaeological window into the Southeast Asian colonization of Madagascar. They additionally suggest that initial Southeast Asian settlement in Africa was not limited to Madagascar, but also extended to the Comoros. Archaeobotanical data may support a model of indirect Austronesian colonization of Madagascar from the Comoros and/or elsewhere in eastern Africa.