The story begins with Bastian fleeing from bullies from his school and hiding in an antique bookstore. Once inside, he meets an old man named Koreander reading a book. After a discussion on the nature of books, Bastian "borrows" a special book from Koreander, called "The Neverending Story". Bastian believes Koreander was trying to keep him away from this book because it was dangerous, but it's obvious that Koreander actually wanted him to take it. The role of the shopkeeper is akin to a keeper of secrets whose purpose is to initiate Bastian into the secret of this book, to help Bastian meet and conquer his fears.
Bastian makes his way to his school; being late he decides to skip class and goes into the school attic to take a look at his special book. From this point on, Bastian is reading in the book, about a world called Fantasia.
Fantasia is under assault by a strange disease or force called 'The Nothing'. We meet three fantastic characters (among which is a Rock-Biter) who are on their way to meet with the Childlike Empress to discuss this menace to their world. Once there, they learn the Empress is sick and dying. Her sickness is apparently linked to the 'Nothing', and the only hope of Fantasia is to send a prophesied hero named Atreyu to find a cure for her. Atreyu rides Falkor the Luckdragon over Fantasia, unknowingly being pursued by Gmork, a giant, sentient wolf. His search leads him to find the 'Sage under the hill', Morla. Upon finding this sage, he learns that he doesn't know how to cure the empress, but that the Southern Oracle might. The problem is that it is very far, and Atreyu has lost his horse Artax in the Swamps of Sadness.
Just as he is about to fall prey to G'mork, he's rescued by Falkor. Falkor brings Atreyu to the Southern Oracle, where he has to cross two trials before being able to speak to the Oracle. The first requires confidence, but the second is supposed to show him his "true self". What he sees is an image of Bastian himself reading The Neverending Story! This is the first real clue that the story of Bastian and of Atreyu are really interconnected. Bastian at that point also starts to seriously realize the book might be as dangerous as Koreander told him it was, and hesitates before reading along. Here we can interpret the trial of Atreyu as being that of Bastian: it's Bastian who has to defeat his own fear of the book and his involvement in it in order for the quest to continue, not Atreyu, who is only slightly perplexed by the image he sees.
The Southern Oracle finally delivers to Atreyu the information he seeks: in order to cure the Empress, she needs a new name. This name can only be given by a human child, not by a resident of Fantasia. It's not quite obvious why this would be, and is only made clear later once we learn more about the nature of Fantasia. The Oracle informs Atreyu he can only find such a child beyond the limits of Fantasia. He sets out with Falkor to cross those, but they encounter the 'Nothing' which has been getting stronger, and are separated. Atreyu ends on the shores of a sea in the ruins of a city where he sees frescoes depicting his own story, including a part he doesn't know about: G'mork. It is not obvious if the paintings were done by people who knew of his quest and observing him, even though the last painting shows an event which happens just after he sees those paintings. It might have been part of a prophecy hinted at the beginning of the journey. It could also hint at another level of intricacy in the story.
After he finishes observing those paintings, he finally meets G'mork. G'mork doesn't recognize Atreyu, and speaks with him, giving him an exposition about the nature of Fantasia and of Atreyu's quest. We learn that Fantasia is the product of humanity's fantasies and dreams (which explains why only a human could act to save the Empress), and that as such it has no limits. We learn that the 'Nothing' is actually humanity's despair and loss of hope, and that G'mork himself is an agent of the forces behind the 'Nothing', hoping to profit from the extinguishing of hope, dreams and fantasies as people without hope are easier to control. It is implied in part that those forces are rooted in the real world, although a more spiritual interpretation is also possible.
This highlights the conflict between dreaming and reality, expressed by Bastian's drawings of unicorns and other beasts, and his involvement in Fantasia contrasted with signs of being torn between the two by now, wanting to believe in Fantasia and the book's power, but also trying to stay aware of reality.
Atreyu kills G'mork, and barely escapes the 'Nothing' to find himself lost among debris of the world of Fantasia. He and Falkor find one of the last remaining structure intact, the Ivory Tower where the Empress lives. He goes in, and the Empress tells him she knew what was required to cure her and save Fantasia, but that the quest was required to make contact with the human child. She calls him by his name, Bastian, and the two stories (that of Atreyu and of Bastian) come together, and Bastian finally decides to believe and gives the Empress a new name (Moonchild). This saves her, but by now Fantasia is gone. She tells him that he can remake it by making wishes, the first one apparently being to restore Fantasia just as it was at the beginning.