Dog-like marsupials (superfamily Borhyaenoidea) were the largest predacious mammals during the Tertiary period in South America. They are critical to our understanding of marsupial origin, phylogeny and palaeobiogeography because they have been related to various marsupial lineages of several continents: didelphoids (mainly New World, but also Europe, Asia and Africa), pediomyid, stagodontids (North America), dasyuroids (Australia) and deltatheroidans (predominantly Asian). These relationships, based mainly on dental morphology, have been discussed and rejected several times. Here we report the discovery of exceptionally well preserved skulls and skeletons, referrable to the didelphoid Andinodelphys, which shed new light on the phylogenetic and palaeobiogeographic origin of dog-like marsupials. The skulls of Mayulestes (boryhyaenoid), Andinodelphys and Pucadelphys (didelphoids) from the early Palaeocene epoch of Bolivia are the oldest known for American marsupials. Comparison of their basicranial anatomy suggests that dog-like marsupials are closely related to an early didelphimorphian radiation in South America, rather than to Asiatic (deltatheroidan), North American (stagodontid), or Australian (dasyuroid) lineages.