Malagasy genetic diversity results from an exceptional protoglobalization process that took place over a thousand years ago across the Indian Ocean. Previous efforts to locate the Asian origin of Malagasy highlighted Borneo broadly as a potential source, but so far no firm source populations were identified. Here, we have generated genome-wide data from two Southeast Borneo populations, the Banjar and the Ngaju, together with published data from populations across the Indian Ocean region. We find strong support for an origin of the Asian ancestry of Malagasy among the Banjar. This group emerged from the long-standing presence of a Malay Empire trading post in Southeast Borneo, which favored admixture between the Malay and an autochthonous Borneo group, the Ma’anyan. Reconciling genetic, historical, and linguistic data, we show that the Banjar, in Malay-led voyages, were the most probable Asian source among the analyzed groups in the founding of the Malagasy gene pool.