Background The largest living lizard species, Varanus komodoensis Ouwens 1912, is vulnerable to extinction, being restricted to a few isolated islands in eastern Indonesia, between Java and Australia, where it is the dominant terrestrial carnivore. Understanding how large-bodied varanids responded to past environmental change underpins long-term management of V. komodoensis populations. Methodology/Principal Findings We reconstruct the palaeobiogeography of Neogene giant varanids and identify a new (unnamed) species from the island of Timor. Our data reject the long-held perception that V. komodoensis became a giant because of insular evolution or as a specialist hunter of pygmy Stegodon. Phyletic giantism, coupled with a westward dispersal from mainland Australia, provides the most parsimonious explanation for the palaeodistribution of V. komodoensis and the newly identified species of giant varanid from Timor. Pliocene giant varanid fossils from Australia are morphologically referable to V. komodoensis suggesting an ultimate origin for V. komodoensis on mainland Australia (>3.8 million years ago). Varanus komodoensis body size has remained stable over the last 900,000 years (ka) on Flores, a time marked by major faunal turnovers, extinction of the island's megafauna, the arrival of early hominids by 880 ka, co-existence with Homo floresiensis, and the arrival of modern humans by 10 ka. Within the last 2000 years their populations have contracted severely. Conclusions/Significance Giant varanids were once a ubiquitous part of Subcontinental Eurasian and Australasian faunas during the Neogene. Extinction played a pivotal role in the reduction of their ranges and diversity throughout the late Quaternary, leaving only V. komodoensis as an isolated long-term survivor. The events over the last two millennia now threaten its future survival.