The evolutionary origin ofHomo floresiensis, a diminutive hominin species previously known only by skeletal remains from Liang Bua in western Flores, Indonesia, has been intensively debated. It is a matter of controversy whether this primitive form, dated to the Late Pleistocene, evolved from early AsianHomo erectusand represents a unique and striking case of evolutionary reversal in hominin body and brain size within an insular environment1,2,3,4. The alternative hypothesis is thatH. floresiensisderived from an older, smaller-brained member of our genus, such asHomo habilis, or perhaps even lateAustralopithecus, signalling a hitherto undocumented dispersal of hominins from Africa into eastern Asia by two million years ago (2 Ma)5,6. Here we describe hominin fossils excavated in 2014 from an early Middle Pleistocene site (Mata Menge) in the So'a Basin of central Flores. These specimens comprise a mandible fragment and six isolated teeth belonging to at least three small-jawed and small-toothed individuals. Dating to ˜0.7 Ma, these fossils now constitute the oldest hominin remains from Flores7. The Mata Menge mandible and teeth are similar in dimensions and morphological characteristics to those ofH. floresiensisfrom Liang Bua. The exception is the mandibular first molar, which retains a more primitive condition. Notably, the Mata Menge mandible and molar are even smaller in size than those of the two existingH. floresiensisindividuals from Liang Bua. The Mata Menge fossils are derived compared withAustralopithecusandH. habilis, and so tend to support the view thatH. floresiensisis a dwarfed descendent of early AsianH. erectus. Our findings suggest that hominins on Flores had acquired extremely small body size and other morphological traits specific toH. floresiensisat an unexpectedly early time.