Malagasy genetic diversity results from an exceptional proto-globalisation process that took place over a thousand years ago across the Indian Ocean. Previous efforts to locate the Asian origin of Malagasy have highlighted Borneo broadly as a potential source, but so far no firm source populations have been identified. Here, we have generated genome-wide data from two Southeast Borneo populations, the Banjar and the Ngaju, together with published data compiled 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 favoured 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 analysed groups in the founding of the Malagasy gene pool.