Gilgamesh is a contender for the oldest recorded story (as suggested by /u/Bearsthtdance). There were certainly stories that were told and passed down before written records, but we are restricted to those that were recorded. You use of the term "passed down," suggesting you want something other than what was simply recorded, but was, rather, part of the oral tradition.

One of the oldest recorded stories that was also passed down is Aarne Thompson Tale Type 318, "The Two Brothers," also known as "The Faithless Wife." The folktale appears in an ancient Egyptian source and was recorded throughout Europe in the nineteenth century. For the Egyptian source see this site as well as this wiki summary. The fact that this folktale appears in Ancient Egypt and nineteenth-century Europe does not imply that the latter is a diffusion from Egypt. Rather, these are simply manifestations of what was probably a well-distributed story without reference to an Egyptian place of origin.

Former anthropologist here. The oldest candidate by far is the Australian Aborigine Dreamtime stories that have been passed down orally. The stories describe events that occurred greater than 10,000 years ago.

" In the case of the Atherton Tableland, myths tell of the origins of Lake Eacham, Lake Barrine, and Lake Euramo. Geological research dated the formative volcanic explosions described by Aboriginal myth tellers as having occurred more than 10,000 years ago. Pollen fossil sampling from the silt which had settled to the bottom of the craters confirmed the Aboriginal myth-tellers' story. When the craters were formed, eucalyptus forests dominated rather than the current wet tropical rain forests.[6][7] (See Lake Euramo for an excerpt of the original myth, translated.)

Dixon observed from the evidence available that Aboriginal myths regarding the origin of the Crater Lakes might be dated as accurate back to 10, 000 years ago.[6] Further investigation of the material by the Australian Heritage Commission led to the Crater Lakes myth being listed nationally on the Register of the National Estate,[8] and included within Australia's World Heritage nomination of the wet tropical forests, as an "unparalleled human record of events dating back to the Pleistocene era."[9]

Since then, Dixon has assembled a number of similar examples of Australian Aboriginal myths that accurately describe landscapes of an ancient past. He particularly noted the numerous myths telling of previous sea levels, including:[10]

the Port Phillip myth (recorded as told to Robert Russell in 1850), describing Port Phillip Bay as once dry land, and the course of the Yarra River being once different, following what was then Carrum Carrum swamp. the Great Barrier Reef coastline myth (told to Dixon) in Yarrabah, just south of Cairns, telling of a past coastline (since flooded) which stood at the edge of the current Great Barrier Reef, and naming places now completely submerged after the forest types and trees that once grew there. the Lake Eyre myths (recorded by J. W. Gregory in 1906), telling of the deserts of Central Australia as once having been fertile, well-watered plains, and the deserts around present Lake Eyre having been one continuous garden. This oral story matches geologists' understanding that there was a wet phase to the early Holocene when the lake would have had permanent water."

http://en.wikipedia.org/wiki/Australian_Aboriginal_mythology

For a good look at almost purely oral traditions when it comes to tales being told, Australian Aboriginal dreamtime stories are probably heading towards some of the oldest. Of course, as oral traditions go, we can't be too sure as to how accurate they are, but several thousand year old cave paintings help to understand both the oral stories, and what keeps them together.

The rainbow serpent is the best example of a long held story... each area had their own interpretation, but all the variations in name and story essentially boiled down to this great rainbow serpent. An anthropologist, Alfred Brown was the first to kind of "bring it" out of being just oral traditions in the 1920's and unfortunately gave it a western type speel. So far as I remember from school, dream time stories don't have a tense... they happen in "everytime", not past or future on their own.

Somebody else who is a historian can answer better, but from what I understand The Epic of Gilgamesh is considered the oldest story recorded. But, there are many ancient Asian texts that are suspected to be older. Before writing, stories were all done over the campfire, oral stories. Sumerians, who were the first to keep records, took the time to write down what we call The Epic of Gilgamesh. Technically we don't even have the full story, we date it back to 18 century BC, but the modern story we use was fleshed out in 13-14 century BC.

Pretty epic story from what I remember.

Edit: Grammar edit 2: Added centuries to the years.