Story
In NetHack, very few actions are mandatory, many features are randomized, and there are many ways to achieve almost anything. This adds to the strategic challenge and makes the game interesting to replay. As a side effect, there is almost no "story" in the sense of most other games.
The few actions that are mandatory have a bit of plot associated with them. However even these few actions don't necessarily have to be done in a particular order.
Contents
Introduction
Every game of NetHack begins with the following text:
It is written in the book of (god X): After the creation, the cruel god Moloch rebelled against the authority of Marduk the Creator. Moloch stole from Marduk the most powerful of all the artifacts of the gods, the Amulet of Yendor, and he hid it in the dark cavities of Gehennom, the Under World, where he now lurks, and bides his time. Your god (god X) seeks to possess the Amulet, and with it to gain deserved ascendance over other gods. You, a newly trained (title X), have been heralded from birth as the instrument of (god X). You are destined to recover the Amulet to your deity, or die in the attempt. Your hour of destiny has come. For the sake of us all: Go bravely with (god X)!
The fact that the text is pretty much the same for every character is a hint that each NetHack god is pretty much interchangeable, except for Moloch.
The in-game introduction somewhat contradicts the introduction provided in the Guidebook, which does not mention the player's god. The Guidebook instead claims that "you have begun to find yourself unfulfilled and distant in your daily occupation" and have started having dreams of adventure. The Guidebook introduction also implies that there is an inn just a few days of travel away from the Mazes of Menace, full of people exchanging stories about the Amulet of Yendor.
The Guidebook's account of the situation has varied; in the past it has said you "have just finished your years as a student at the local adventurer's guild" and were sent to recover the amulet by the guildmasters. In later versions you are told that you have "exhausted your own meager financial resources, as well as those of your parents", compelling you to turn to adventuring.
Upper dungeons
The start of the game is dominated by the search for food and equipment. The story is simply "survive".
Each dungeon is guaranteed to contain the Gnomish Mines and Sokoban. The player does not need to interact with any of them, but they provide helpful items and flesh out the setting. The mines are profitable enough to support an entire underground town. Meanwhile in the main dungeon, there is apparently enough economic activity to support the Oracle, several shops, and the Keystone Kops.
Quest
After gaining sufficient experience, the player must return to their homeland to embark on a quest specific to their role. The quest nemesis carries the Bell of Opening in addition to the role-specific quest artifact, making the quest mandatory.
The quest requires the player to live up to the morals of their people, and generally concludes with killing the quest nemesis and taking the artifact. However, it is entirely possible for player to let the nemesis live, take the Bell of Opening while leaving the quest artifact behind, or even kill the quest leader. This is usually tougher than just following the plot normally. In fact angering or killing the quest leader before obtaining the Bell of Opening can render the game unwinnable.
Medusa's Island
Somewhere below the Quest portal is a level full of water and islands, one of which is inhabited by Medusa. Even if Medusa's Island is skipped by digging, the player will have to traverse it on the way back up. So the player must eventually have the resources to traverse water and get past Medusa. Her statue of Perseus suggests that their showdown did not follow the Greek legend.
Castle
At the bottom of the Dungeons of Doom, is a castle full of soldiers and monsters. They are guarding a wand of wishing and the trapdoors to Gehennom, among other things.
Gehennom
Below the Castle is Gehennom, the fiery and labyrinthine domain of Moloch. The player's god can't help them here, but usually at this point the player's ascension kit is almost complete.
Valley of the Dead
The Valley of the Dead is full of hordes of undead and a surprisingly polite aligned priest of Moloch. Despite being a servant of Moloch, the priest is peaceful and willing to provide the player with divine protection in exchange for gold. What this says about the clergy and Moloch himself is left for the player to interpret.
Demon Princes
Gehennom has many high-level demons with entire lairs to themselves, many of whom are also willing to leave the player alone in exchange for a bribe.
Vlad's Tower
Vlad the Impaler holds the Candelabrum of Invocation, so facing him is mandatory. His tower is not strictly in Gehennom, but is accessed from Gehennom through a magic portal.
Wizard's Tower
Another mandatory foe is the Wizard of Yendor himself, a powerful sorcerer who lives in a tower with multiple aquariums, a beehive and a zoo. The Wizard holds the Book of the Dead, and perhaps not coincidentally he also knows how to rise from the dead.
Vibrating Square and the Sanctum
At the lowest level of Gehennom is a vibrating square, where the player must complete the Invocation ritual to access an even lower, even more secret level.
The floor shakes violently under you! The walls around you begin to bend and crumble! You are standing at the top of a stairwell leading down!
Here, in Moloch's Sanctum, after pushing through hordes of monsters, priests and traps, the player sees the prize coveted by the gods themselves: the Amulet of Yendor.
Endgame
Returning to the surface
The player can try offering the Amulet of Yendor back to Moloch. This is pointless, as Moloch already had the Amulet right at the start. He won't appreciate the gesture, either:
Moloch shrugs and retains dominion over <your god>, then mercilessly snuffs out your life.
Simply possessing the Amulet does not grant much power at all: definitely nothing that assists in combat. It is an artifact with little use to mere mortals. To really reap the rewards of the Amulet the player must leave the Dungeons of Doom. The player can't win by going home through the quest portal, and the quest leader will say so. For example, here is what Neferet the Green will tell a player holding the Amulet:
"Congratulations, <playername>. I always knew that if anyone could succeed in defeating the Wizard of Yendor and his minions, it would be you. "Go now, and take the Amulet to the astral plane. Once there, present the Amulet on the altar of <Thoth|Anhur>. Along the way you shall pass through the four elemental planes. These planes are like nothing you have ever experienced before, so be prepared! "For this you were born, <brother|sister>! I am very proud of you."
The Elemental Planes are only accessible by climbing all the way to the upstairs of dungeon level 1 while carrying the Amulet. The Planes are extremely hazardous: the player will have to dig, fly and perhaps even swim past a multitude of monsters, including a revived Wizard of Yendor, before reaching the final level of NetHack.
Astral Plane
You arrive on the Astral Plane! Here the High Temple of (god X) is located. You sense alarm, hostility, and excitement in the air!
On the Astral Plane, each of the gods has an army of angels, priests and even their own adventurers who are all ready to fight to the death for the Amulet. Even more dangerous are the Riders: Famine, Pestilence and Death. They have a more personal rivalry with the player.
If the player offers the Amulet to the wrong god, they "escape in celestial disgrace". However switching one's religion with the helm of opposite alignment makes things entirely fine with their new deity: as hinted at the beginning, the gods are ultimately interchangeable. Players who haven't interacted with their god at all have no alternate path to success, but their sense of independence won't be forgotten.
When at long last the player offers the Amulet of Yendor on their god's high altar, their story concludes with this:
You offer the Amulet of Yendor to [your god]... An invisible choir sings, and you are bathed in radiance... The voice of [your god] [booms out/booms/thunders/rings out]: "Congratulations, mortal!" "In return to thy service, I grant thee the gift of Immortality!" You ascend to the status of Demigod[dess]...
