We use story very broadly to mean any sort of explanation, theory, prediction, justification or verbal description. Any narrative inevitably contains these elements, whether it is a myth, a story intended to entertain, a persuasive political speech, or a scientific publication.
Important characteristics of stories are that they are inherently verbal (we could speak them if we chose to), and that they have an ambiguous relation to the Truth.
We argue that creation of story is nearly synonymous with Consciousness. According to The Interpreter Theory, the only function of consciousness is making story. This is at odds both with intuitive and philosophical concepts of conscious free will (see Determinism vs. Free Will), but is consistent with many streams of puzzling evidence from neuroscience, psychology and behavioral economics, and with evolutionary theories of the origin of consciousness. See Representational Opacity.
Because story is fundamentally verbal, it is also fundamentally social. The ability to speak is useless without someone to communicate with. See The Argumentative Theory and The User Interface Analogy.
Fictional stories are a natural outgrowth of the necessary ability to explain our actions to others and to convince them to agree with us in practical matters. Looking at the actions of the interpreter as story-telling gives a more nuanced way of viewing those times when the interpreter says something that isn't exactly true.
Unless we're consciously manipulative, we tell stories either to get people to think the way that we do, or to establish empathy by getting people to think that we are thinking same as they do. In storytelling, it is understood that the ends justify the means. You can say whatever you need to in order to carry the story payload. It is understood that you won't muddy the message with conflicting evidence. Of course, getting people to think like you is self-serving, especially when your thoughts are self-serving. But getting people to think like you is also crucial for the transmission of culture. Trying to get people to think like you is fundamental to communication, and thus to being human. You could say it is a moral imperative.
The question is where truth and deception come into storytelling. A good story carries truth, which normally happens only when the teller has a true belief. Can we recognize some stories as deceptive “lies” independent of whether they happen to be true? The canonical lie is making a statement which you believe to be false to influence other's behavior to your self-serving ends, but a lie doesn't have to be false, it only has to be a deliberately deceptive story.
In Evolutionary Psychology there is much investigation of deceptive, self-promoting behavior, and in social psychology the related concept of Motivated Reasoning. Our more positive spin is that, first of all, none of us know whether we are right or not, and we don't even know most of what we think. All we know is that we can generate a story that is a useful summary of some of our understandings. Second, presenting our thoughts in a persuasive way is a creative act, the fundamental mechanism of cultural transmission, and hence Cultural Evolution.