If folktales count, then The Poor Man of Nippur (c. 1500 BCE) probably beats the Egyptian Tale of Two Brothers by at least a few centuries. It's certainly not mythological in any modern sense, being a simple trickster tale of a clever beggar exacting revenge on an ungrateful mayor by tricking him three times (and consequently beating him up worse and worse every time).
Whether it was "meant to be believed to be true," of course, is another matter. While modern readers would certainly assume The Poor Man of Nippur to be fictional, and ancient audiences were probably no different in this respect, the tale contains no supernatural or otherwise obviously unrealistic elements that would clearly mark it as such. For all we know, maybe there really was a poor man named Gimil-Ninurta in ancient Nippur who was mistreated by the mayor and took revenge on him, even if the details of the story might have been somewhat embellished in the telling.
Still, 1500 BCE is kind of late as far as Mesopotamian history and culture goes. Surely we can find something earlier? After all, Sumerian literature goes back to around 2500 BCE in its earliest written forms (and probably much further via oral tradition, even if we can't really tell how far).
The problem here becomes one of deciding which tales count as "mythology" and which don't. Does it matter if a god briefly appears in the story? Does it matter if the hero of the story is described as "two parts god, one part man", as Gilgamesh famously was in some versions of his epic, or is deified in later myths? Does it matter if the story contains or references elements (such as the flood myth) that have obvious parallels in later religious texts like the Old Testament?
Still, even if we discount all the Sumerian epic tales of Enmerkar, Lugalbanda and Gilgamesh (not to mention the numerous tales of Inanna, even the ones where she's portrayed as little more than an ordinary young woman) as too mythological, there are also more down-to-earth kinds stories in Sumerian literature that I feel should probably qualify.
One such genre of stories are the so-called E-dubba texts, which are basically ancient children's literature. Written in Sumerian, but dating from the Old Babylonian period (c. 2000–1600 BCE), when Sumerian was still taught in scribal schools as a literary language (much as Latin was until recently taught in western schools, and sometimes still is), they describe the life of a scribal student and were meant to be copied by those very students as learning exercises.
Their content often features a moralistic and motivational tale of success through hard work and learning, as in the E-dubba A ("Schooldays") text, where a student struggles in school (and gets beaten a lot for his failures) and is about to give up his studies before receiving praise from his father and his teacher for his perseverance. That said, they also often had a humorous side, as in the E-dubba B text, a.k.a. "The Scribe and his Perverse Son" (which I unfortunately couldn't find a good online translation for), which features a long and colorful litany of Sumerian insults (including such gems as "a dog who licks his own penis" and "smelly buttocks that stink and make everything stink") that must surely have appealed to the students in their early teens who would have been tasked with copying the text.