The findings have allowed them to map how the continent may have looked around 10,000 years ago.
Oral folklore tells how the Great Barrier Reef once formed part of the coastline of north east Queensland, while Port Phillip Bay in Victoria was once a rich place for hunting kangaroo and opossum.
Researchers have found other stories from all over the continent that mirror how the landscape dramatically changed towards the end of the last ice age.
They say at this time sea levels rose as a result of the melting of the huge ice caps that covered much of the northern hemisphere around 10,500 years ago.
The researchers now believe that these stories could constitute some of the oldest accurate oral histories in the world, passing through some 300 generations.
The finding is remarkable as many anthropologists believe that exaggeration and Chinese whispers often distort oral history so severely that they can no longer be reliable if they are older than 1,000 years old.
However, Dr Nick Reid, a linguist at the University of New England, has found that the stories of Australian Aborigines are astoundingly accurate.
Hidden within myths of seagull gods and ancestral heroes causing seas to rise and great floods are details of how the landscapes looked before the time.
Dr Reid studied 18 traditional Aboriginal stories and found that they seemed to coincide with true geological events.
Writing for the Conversation, he said: 'How do we know that these stories are authentic? We suggest that because they all say essentially the same thing, it is more likely that they are based on observation.
'All tell of the ocean rising over areas that had previously been dry. None tell stories running the other way - of seas falling to expose land.
'The huge distances separating the places from which the stories were collected - as well as their unique, local contexts - makes it unlikely that they derived from a common source that was invented.'
Among the stories examined by Dr Reid and his colleague Professor Patrick Nunn, a geographer at the University of the Sunshine Coast, were a tale told by the Ngarrindjeri people.
It tells how an ancestral hero called Ngurunderi chased his wives on foot to Kangaroo Island, where he angrily rose the seas, turning the women into rocks that now jut out of the water between the island and the mainland.
If this is based on true geographical changes, it would mean it originated at a time when seas were around 100 feet lower than they are today, making it around 9,800 to 10,650 years old.
Another story describes how the Wellesley Islands in the southern Gulf of Carpentaira was once part of a peninsular that jutted out from the mainland.
The story tells how a 'seagull woman' called Garnguur swept down and dragged her raft across the neck of the peninsula to allow the sea pour in.
Other stories written down in early colonial times also tell of kangaroo and emu hunting grounds that were later flooded by the rising sea water.
The Narrangga people of the York Peninsula of southern Australia told stories that recalled a time when the Spencer Gulf was actually a marshy part of the mainland that was dotted with freshwater lagoons that attracted rich wildlife.
Dr Reid estimates that these stories could date from between 9,550 to 12,450 years ago.
Similarly other stories tell how the area of Port Phillip Bay in Victoria was also a marshy part of the mainland, making them around 7,800 to 9,350 years old.
A tale told by the Tiwi people describe how an old woman followed by a flood of water crawled between the islands of Brathurst and Melville, now off the coast of Australia's Northern Territory.
This, the researchers say, could be telling how the islands were settled and then cut off from the mainland around 8,200 to 9,650 years ago.
A traditional story from Western Australia tells how Rottnest, Carnac and Garden Islands, once formed part of the mainland and the land was covered in trees.
The story says that a fire took hold and burned with such intensity that the ground split, allowing the sea to rush in.
Dr Reid and his colleagues estimate this would have occurred at least 7,500 to 8,900 years ago.
Dr Reid said that their findings suggest that other traditional oral histories passed down in indigenous languages around the world could also provide similar nuggets of truth.
He said: 'The extraordinary care with which Aboriginal people have passed down these stories over previously unimaginable time depths forces a rethink of the ways in which such oral traditions have previously been dismissed.
'While these examples should not be regarded as a licence for the incautious interpretation the antiquity of oral traditions, or indeed for the belief all such stories have empirical foundations, it does allow for some traditions in some cultures to have survived for far longer than it was once thought any such traditions could.'
Another ancient oral history among the Klamath of Oregon is thought to be around 7,700 years old.
Professor Nunn added that there could also be stories traditional cultures in India that could be equally as old.
THE GREAT BARRIER COASTLINE
Several stories tell how the Great Barrier Reef was once the original coastline of north east Queensland.
Stories told by the Googanji people describe how a river entered the sea near to what is now called Fitzroy Island.
The Yidindji people who lived in the Cairn's area of Queensland also tell how Fiztroy Island was once called 'gabar', or lower arm.
They told how it had once been part of a promontory sticking out from the mainland while nearby Green Island was four times larger and the Island is now all that is left sticking out the ocean.
They also describe a place called 'mudaga', or pencil cedar, between Fitzroy Island and King Beach after the trees that once grew there.
So it was actually the aborigines who invented the SUV?