Crannogs were fortified settlements constructed on artificial islands in lochs.
It was thought they were first built in the Iron Age, a period that began around 800 BC.
But four Western Isles sites have been radiocarbon dated to about 3640-3360 BC in the Neolithic period - before the erection of Stonehenge's stone circle.
The prehistoric monument in Wiltshire is one of Britain's best-known Neolithic features. Stonehenge's stone circle was erected in the late Neolithic period, about 2500 BC.
Another famous Neolithic site is Skara Brae, a village in Orkney inhabited between 3200 BC and 2200 BC.
Archaeologists Dr Duncan Garrow, of the University of Reading, and Dr Fraser Sturt, from the University of Southampton, investigated four crannog artificial islands in the Isle of Lewis in the Western Isles.
At one of the sites, well-preserved Neolithic pottery had previously been found on the loch bed by Chris Murray, a former Royal Navy diver who lives in Lewis.
The archaeologists' investigation included making underwater surveys and carrying out excavations at the sites to obtain "conclusive evidence of artificial islet construction during the Neolithic".
The archaeologists, whose research has been published in the journal Antiquity, said the crannogs represented "a monumental effort" through the piling up of boulders on the loch bed, and in the case of a site in Loch Bhorgastail the building of a stone causeway.
They said it was possible other Scottish crannogs, and similar sites in Ireland were also Neolithic.
Previously it was thought crannogs were built and re-used over a period of 2,500 years from the Iron Age to the post-medieval period.