I see two questions here – did fiction or non-fiction narratives come first (something that we can only speculate about because it is in prehistory)?

And, is the oldest written source for a narrative fiction or non-fiction?

Both these questions are entwined with two international forms of folk narrative, what we in English refer to as the folktale and the legend. This from my Introduction to Folklore, which I used when teaching folklore at university:

Legends – or Sagen as the profession often prefers – are generally short, single-episodic stories told chiefly in the daytime. More importantly, the teller intended the listener to believe the story. Legends often have horrible ending to underscore the story’s important message. Many of them are, after all, meant to be instructive, to serve as warnings in some way. These types of stories are not necessarily long-lived. Their point is to reinforce and prove the legitimacy of a belief. Nonetheless, some legends take on a traditional character, can become multi-episodic, and migrate over considerable spans of time and space.

Folktales – or Märchen, again using the German, technical term – are longer stories with more than one episode. They are restricted, in theory at least, to evening presentation. A folktale is not to be believed, taking place in a fantastic setting. The European folktale also requires a happy ending, the cliché of “happily ever after.” Any given folktale can be told with considerable variation, but they are traditional in basic form, and folklorists have spent decades tracing the history and distribution of these stories.

Let’s consider at least one of the earliest recorded narratives, the story that appears in several texts and is known as “The Epic of Gilgamesh.” Is this fiction or non-fiction? Today, it is typically placed in the category of “myth,” but what that term means depends on the eye of the beholder. Many myths from the ancient world were apparently legends (etiological – the origin of things; heroic; historical; or simply dealing with the contemporary or near contemporary supernatural) but perceiving how these stories were taken over centuries of generations can be a challenge. Other myths may have been intended as fiction, but again, intent and perception at the time can be difficult to determine. Things may have shifted, for folklore is in constant flux.

In general, I would see “The Epic of Gilgamesh” as something that was generally intended to be believed, so it would be non-fictional. Others here may put forward older recorded narratives, but these issues provide a context for how one needs to grapple with the question.

Then there is the question about prehistory, which is necessarily speculative. Many have embraced the idea that humanity should be classified as a species as Homo narrans – the storytelling human, an idea put forward as early as 1967 by the ethnographer, Kurt Ranke. The point is well taken: separating our humanity from our inclination to tell stories is difficult, and we can imagine that the art of storytelling is very old.

The French folklorist, Julien d’Huy has attempted to reconstruct many stories that he believes are paleolithic, including something he refers to as “The Cosmic Hunt”. Were these intended as fiction or non-fiction? Sadly, the storytellers and their audiences can’t tell us. I’m inclined to see these as legendary, narratives generally told to be believed.

Are these then the oldest? Even d’Huy can’t answer that, nor, I suspect, would he try. Legends can be extremely brief, and they can often be a reaction to something that has happened and that others need to be warned about: “Don’t go over there for a supernatural entity who is dangerous dwells there. You should hear what happened to my friend’s cousin … etc.” Fictional narratives tend to be more elaborate. I speculate, consequently, that legends came before folktales, but this is, as indicated, mere speculation.