Before the Spanish discovery, archaeologists thought that humans had not entered Europe prior to 500,000-700,000 years ago.
Some suggest that the first Europeans crossed the Straits of Gibraltar from Africa by swimming or on rafts. At times during the early Stone Age, the straits were only three miles wide but would still have had dangerous currents.
So far an archaeological team, from academic institutions in Murcia, Madrid and Catalonia has discovered more than a dozen sharp-edged flint tools and dozens of waste fragments from tool manufacture.
On one site this summer they found a series of sharp flint artefacts scattered around the remains of a hippopotamus on the banks of ancient river channels which used to flow into a now vanished 50-mile long lake near the small Andalucian town of Orce, 70 miles east of Granada.
The discovery of the Orce stone Age humans, though unexpected, does fit into the emerging pattern of the earliest human exit from Africa.
The first proto-humans seem to have emerged in Ethiopia by 4.4 million years ago. The first tools were being made some 2.7 million years ago. The first more developed humans, members of our own genus, Homo, had probably evolved by 2.5 million BC also in east Africa.
Then shortly before or around two million years ago, humans appear to have spread out from the African continent. Archaeologists recently detected traces of these early "colonists" of 2.1-2.5 million years ago in northern Pakistan, at 1.8 million years ago in the Caucasus Mountains and possibly at around 1.9 million years ago as far east as Java.
The earliest date being suggested for Orce is 1.6 million years, which would fit in very well with this first exit from humanity's African "Eden".
Alternatively Orce could date from around 1.1 million years ago, which would still make it the oldest human site in Europe. Prior to the discovery of the Orce material, what was then Europe's earliest known human occupation site, Isernia in central Italy, was dated to between 500,000 and 750,000 years. Britain's Boxgrove Stone Age site and several others in Europe all date from approximately 500,000 BC. Now, however, the attention of the archaeological world is turning to Orce, following a major conference held at the site last month.
A research programme is now planned by the Spanish to provide more evidence to indicate which of the two dates - 1.6 million or 1.1 million - is correct.
The hunt has also started at Orce for the skeletal remains of these first Europeans - and only then will archaeologists and anthropologists be able to work out whether these early colonists were the ancestors of the humans who had colonised northern Europe by half a million years ago. So far five bone fragments of possible human origin have been unearthed.
Some archaeologists suspect that the early colonists may have been a species of human different from the later wave. Certainly they appear to have used very different stone tool technology. But it is likely that neither is directly ancestral to modern man (Homo Sapiens which evolved back in Africa only 100-150,000 years ago) - for both the early (1.6-1.1 million BC) and later (500,000- 700,000BC) "pre-modern" colonists became extinct.
The Orce excavations are being directed by Dr Joseph Gibert of the Dr M Crusafont Palaeontological Institute at Sabadell, near Barcelona. Academics from the Universities of Murcia and Madrid, and from France, are also involved.
The site itself is located in an arid mountain area criss-crossed by steep ravines in a remote area of southern Spain.
The age of the Orce material has been worked out using a system known as palaeo-magnetic dating in which known reversals in Earth's polar magnetism are detected in the geological deposits in which the human flint artefacts were found. "The Orce material appears to be the earliest evidence of human activity thus far found in Europe - and is of great archaeological importance," said Dr Derek Roe, an expert on the early Stone Age at Oxford University, who has been advising the Orce excavation team.