There is good scientific consensus that the modern human species (Homo sapiens sapiens) first evolved in Africa, left about 60,000 years ago, and arrived in southeast Asia about 45,000 years ago.
However, other human species had left earlier: Homo erectus first left Africa about 2 million years ago, spread widely, and was to be found as recently as 50,000 years ago in Java. (By contrast, Neanderthals, homo sapiens neanderthalensis, reached Europe between 600,000 and 350,000ya, lasting to 30,000ya. Tellingly, sub-Safaran Africans have been found to have no Neanderthal DNA, while all other humans have 1-4% DNA from Neanderthals.)
Australopithecus afariensis and Homo floriensis (from Wikipedia)
More recently, the find of Homo floresiensis on the Indonesian island of Flores, has been dated to as recently as 13,000ya, going as far back as 94,000ya. This is well before the emergence of modern humans, although evidence suggests the two species could have lived in close proximity for a time.
The H floresiensis remains are in fact so recent that they comprise original material, as opposed to fossils, which are rock which replaced (at a later point) eventually-disintegrating bone matter.
Because of the spread of H erectus, it has been speculated that this more recent find is descended from H erectus, and still underwent a dwarfism typically associated with animal species that have migrated to island environments.
Adam Brumm of the University of Wollongong reported recently in Nature a find of tools in Wolo Sege in Flores that pushed back hominid (which is not to say H sapiens sapiens) occupation of Flores to at least 1,000,000ya.
Recently on ABC Radio, Brumm commented that the working hypothesis is that the tools belonged to an ancestor of H Floresiensis, since they were the only ones there that far back. He also suggested that, rather than descending from H erectus, H floresiensis descended from an australopithecus species, so is hominid rather than human (Australopiths having evolved into the several homo species, and died out, about 2mya).
The important takehomes are that pre-hominids may have left Africa much earlier than hominds, and that H floresiensis is likely more distantly related to humans than any other homo species. (Note: current thinking has chimpanzees diverging from humans about 5-6mya, which would put floresinensis divergence at 2-5mya.)
If Brumm's comments are correct, there may need to be a name change from H to A floresiensis.
This accords well with plenty of the other evidence on H floresiensis (albeit floresiensis likely underwent further evolution apart from dwarfism).
Brumm called it an exciting time to be in the field, but also said they now needed new sedimentary basin finds [in Flores] to explore the period from 2mya to 1mya. Despite the science, paleontology finds are still a matter of skilled luck as much as anything else.
Other references:
An ABC report on the tool finds;
anthropologist John Hawkes comments on the tool finds