Excavations at Liang Bua, a large limestone cave on the island of Flores in eastern Indonesia, have yielded evidence for a population of tiny hominins, sufficiently distinct anatomically to be assigned to a new species, Homo floresiensis. The finds comprise the cranial and some post-cranial remains of one individual, as well as a premolar from another individual in older deposits. Here we describe their context, implications and the remaining archaeological uncertainties. Dating by radiocarbon (14C), luminescence, uranium-series and electron spin resonance (ESR) methods indicates that H. floresiensis existed from before 38,000 years ago (kyr) until at least 18 kyr. Associated deposits contain stone artefacts and animal remains, including Komodo dragon and an endemic, dwarfed species of Stegodon. H. floresiensis originated from an early dispersal of Homo erectus (including specimens referred to as Homo ergaster and Homo georgicus) that reached Flores, and then survived on this island refuge until relatively recently. It overlapped significantly in time with Homo sapiens in the region, but we do not know if or how the two species interacted.