If you’d like a little background on the oldest hominid fossils discovered outside of Africa, you might enjoy this article from the Chicago Tribune. It describes the work of paleoanthropologist David Lordkipanidze at the archaeological site at Dmanisi in the country of Georgia.
Dmanisi is a rare and rich site; workers there have found five hominid skulls in an area about the size of a large classroom, whereas in Africa you’d likely have to cover a hundred square miles to find that many. The skulls and other bones date back to around 1.8 million years ago, and represent the earliest known hominids to have left Africa. When these bones were first dated, they aroused a great deal of interest because no one at the time thought that there were any hominds outside of Africa that long ago. These relatively small-brained early humans called into question the idea that having a bigger brain was linked to the first migration out of Africa. Sorting out their place in the evolution of humankind has been and will likely continue to be interesting. They might represent a new species, tentatively dubbed Homo georgicus, or maybe a subspecies of Homo erectus.
This news article from the Leakey Foundation, written in 2002 about one of the newly discovered skulls, has more info and a photo.