Historical patterns of diversity, biogeography and faunal turnover remain poorly understood for Wallacea, the biologically and geologically complex island region between the Asian and Australian continental shelves. A distinctive Quaternary vertebrate fauna containing the small-bodied hominin Homo floresiensis, pygmy Stegodon proboscideans, varanids and giant murids has been described from Flores, but Quaternary faunas are poorly known from most other Lesser Sunda Islands. We report the discovery of extensive new fossil vertebrate collections from Pleistocene and Holocene deposits on Sumba, a large Wallacean island situated less than 50 km south of Flores. A fossil assemblage recovered from a Pleistocene deposit at Lewapaku in the interior highlands of Sumba, which may be close to 1 million years old, contains a series of skeletal elements of a very small Stegodon referable to S. sumbaensis, a tooth attributable to Varanus komodoensis, and fragmentary remains of unidentified giant murids. Holocene cave deposits at Mahaniwa dated to approximately 2000-3500 BP yielded extensive material of two new genera of endemic large-bodied murids, as well as fossils of an extinct frugivorous varanid. This new baseline for reconstructing Wallacean faunal histories reveals that Sumba's Quaternary vertebrate fauna, although phylogenetically distinctive, was comparable in diversity and composition to the Quaternary fauna of Flores, suggesting that similar assemblages may have characterized Quaternary terrestrial ecosystems on many or all of the larger Lesser Sunda Islands.