The prologue depicts the burning of a small village in the Fairfield Lowlands by the Legion of the Fallen, an undead army under the command of Necros, a necromancer who sold his soul to the dark gods in exchange for unparalleled sorcerous aptitude.
A young boy named Drake, the only survivor of the massacre, escapes into the forests of Duskwood and roams Ardon for years, seeking revenge against the undead. During an attack on his camp by ogres, Drake is saved by the blind hermit Nomandi, who becomes Drake's mentor over the next few years.
The first playable portion of the PlayStation version takes place in Stronghold following Drake's capture by shamblers, the lowliest of the undead. Drake escapes Stronghold with the aid of Celestia, Lady Archon of Citadel, and is enlisted into the ranks of the valiant crusaders under her rule.
Traveling to Corantha, city of the dwarves, Drake enters an agreement with Prince Dain Stonefist against the Ironpick rebels who attack the city from within, exposing Dain's brother, Tor, as an agent for the Legion. Traveling to Duskwood, Drake retrieves the Coranthan Scepter of Regency from a band of ogres with the aid of the insectoid dashers and their leader, Tamris.
Returning to Corantha, Drake discovers that earth elementals have awakened while both Dain and Tor have gone missing, with the Ironpicks continuing to battle the Stonefists. Drake navigates the deep mines and defeats the revenant of King Aiden, Dain's recently slain father raised through necromancy, thereby saving the Prince and gaining Corantha's favor against the undead.
Returning to Citadel, Drake is then tasked with retrieving a talisman named the "Star of Erathia" from the northern Glaciers to aid in the war effort. After doing so, he returns to Duskwood to combat the Legion in the grub-infested tunnels below the forest floor, successfully destroying Necros' supply lines. With this victory in hand, he travels back to Stronghold, to aid Celestia's crusaders and the dwarves in the final siege against the Legion's bastion.
Upon his arrival, Drake encounters Celestia fleeing the battlefield, and finds the leader of the crusaders, Captain Ursan, missing. Nevertheless, while the crusaders fight on the front lines, he penetrates the walls of Stronghold, battling the Legion's armies. Drake finally comes face-to-face with Necros in Stronghold's depths, but the wily necromancer departs through a portal, leaving the crusader to combat his lieutenants. Drake claims victory, and follows the necromancer through the portal.
Finding himself in Necros' floating battleship, Drake discovers Necros' forces docked at a massacred, Legion-occupied Citadel. Drake fights his way to Celestia's throne room, finding no sign of the Lady Archon. He then comes upon a hidden chamber filled with arcane, futuristic mechanisms, discovering an elevator leading to an outer-world location. There, he finds Necros standing before an enormous interdimensional portal - the Kreegan Gate.
Necros claims that Celestia sought the power of the kreegans just as much as he did, taunting Drake into doing battle. Instead of attacking the invincible necromancer, Drake destroys the Gate itself, causing a rift in space. Drake targeted the outer pillars with Exploding Gems right where the bolts of electricity travel to the Kreegan Gate. Necros is drawn through the Gate's portal, screaming promises of revenge against Drake. Drake, triumphant, returns to Citadel, finding the crusaders victorious against the Legion. With Celestia still in hiding from Necros and her newly enlightened armies, Drake becomes the Lord Archon of Citadel, and the new leader of the crusaders.
Numerous aspects of the storyline differ in the Windows version. Before reaching the Citadel, Drake must pass through the small village of Cador Sul, which is not present in the PlayStation version. Also, Prince Dain must be rescued from the Ironpicks before he can be spoken to, and Tor is not present. Two dungeon-like locations, the Catacombs and the fallen Starship, are accessible only in the Windows version. Ursan plays a larger role, Celestia does not flee Citadel and the final battle takes place on Necros' Battleship, with no mention of the Kreegan Gate.