Burkholderia pseudomallei, an environmental bacterium that causes the deadly disease melioidosis, is endemic in northern Australia and Southeast Asia. An increasing number of melioidosis cases are being reported in other tropical regions, including Africa and the Indian Ocean islands. B. pseudomallei first emerged in Australia, with subsequent rare dissemination event(s) to Southeast Asia; however, its dispersal to other regions is not yet well understood. We used large-scale comparative genomics to investigate the origins of three B. pseudomallei isolates from Madagascar and two from Burkina Faso. Phylogenomic reconstruction demonstrates that these African B. pseudomallei isolates group into a single novel clade that resides within the more ancestral Asian clade. Intriguingly, South American strains reside within the African clade, suggesting more recent dissemination from West Africa to the Americas. Anthropogenic factors likely assisted in B. pseudomallei dissemination to Africa, possibly during migration of the Austronesian peoples from Indonesian Borneo to Madagascar ~2,000 years ago, with subsequent genetic diversity driven by mutation and recombination. Our study provides new insights into global patterns of B. pseudomallei dissemination and adds to the growing body of evidence of melioidosis endemicity in Africa. Our findings have important implications for melioidosis diagnosis and management in Africa.