Australian dinosaurs have played a rare but controversial role in the debate surrounding the effect of Gondwanan break-up on Cretaceous dinosaur distribution. Major spatiotemporal gaps in the Gondwanan Cretaceous fossil record, coupled with taxon incompleteness, have hindered research on this effect, especially in Australia. Here we report on two new sauropod specimens from the early Late Cretaceous of Queensland, Australia, that have important implications for Cretaceous dinosaur palaeobiogeography. Savannasaurus elliottorum gen. et sp. nov. comprises one of the most complete Cretaceous sauropod skeletons ever found in Australia, whereas a new specimen of Diamantinasaurus matildae includes the first ever cranial remains of an Australian sauropod. The results of a new phylogenetic analysis, in which both Savannasaurus and Diamantinasaurus are recovered within Titanosauria, were used as the basis for a quantitative palaeobiogeographical analysis of macronarian sauropods. Titanosaurs achieved a worldwide distribution by at least 125 million years ago, suggesting that mid-Cretaceous Australian sauropods represent remnants of clades which were widespread during the Early Cretaceous. These lineages would have entered Australasia via dispersal from South America, presumably across Antarctica. High latitude sauropod dispersal might have been facilitated by Albian-Turonian warming that lifted a palaeoclimatic dispersal barrier between Antarctica and South America.