On the first day, man was granted a soul, and with it, clarity. On the second day, upon Earth was planted an irrevocable poison; a soul-devouring Demon.
King Allant the twelfth, by channeling the power of souls, brought unprecedented prosperity to his northern kingdom of Boletaria. That is, until the colorless Deep Fog swept across the land. Boletaria was cut off from the outside world, and those who dared penetrate the Deep Fog never returned. But Vallarfax of the royal Twin Fangs broke free from the fog and told the world of Boletaria's plight. That the Old King had aroused the Old One, the great beast below the Nexus, from its eternal slumber. And that a colorless fog had swept in, unleashing terrible Demons. The Demons hunt down men and claim their souls. Those who lose their souls also lose their minds. The mad attack the sane, and chaos reigns. Vallarfax spoke of the enticing power of the Demon souls. Each time a Demon claims a human soul, the Demon's own soul is invigorated by the life force. And the power of a mature Demon Soul is beyond human imagination. The legend spread quickly. Mighty Warriors were drawn to the accursed land, but none have returned. Biorr of the Twin Fangs, Yurt the Silent Chief, Sage Urbain, Scirvir the Wanderer, the Sixth Saint Astraea and her knight Garl Vinland, and Sage Freke the Visionary. The colorless Deep Fog slowly creeps beyond Boletaria's borders. Humankind faces a slow and steady extinction. The Deep Fog will eventually swallow all lands near and far. But Boletaria has one final hope. A lone warrior who has braved the baneful fog… Has the land found its savior, or have the Demons found a new slave?
A gentle, disembodied voice addresses the player: "Brave soul, who fears not death. I shall guide you so that you may lull the Old One back to slumber."
The game is set in the kingdom of Boletaria, ruled by the aging King Allant XII (the game's main antagonist). Because of his greed, the king searched for power and prosperity through a dark ritual of channeling the power of souls that brought unprecedented prosperity to Boletaria, until the "Deep Fog" covered the land's outskirts, cutting off the kingdom from the outside world. Neighboring kingdoms sent scouts to investigate but none returned after entering the fog. It was only after Vallarfax of the royal Twin Fangs broke free from the fog that the rest of the world could be told of Boletaria's plight. By channeling souls, King Allant had awakened the Old One, a great demon residing below the Nexus. With the Old One's awakening, a dark fog had swept in that within it unleashed demons who feasted on the souls of mankind, where those left alive without a soul became insane and violent. Without resistance, the fog slowly begins to spread beyond Boletaria.
The Maiden in Black beckons to the Old One. Many brave warriors attempted to breach the fog and save Boletaria while others were swayed at the prospect of harnessing the demon's souls; either way, many were lost to the fog. The player takes control of one such warrior who breaches the fog and enters the lost kingdom; however, after entering the palace botanical gardens, the lone hero adventurer is confronted by a vile demon, The Vanguard. If the adventurer manages to defeat the Vanguard, they are killed by the Dragon God, another ville demon in the form of a massive dragon. After dying, the hero, now in soul form, appears in the Nexus. In the Nexus, they are greeted by the Maiden in Black, a mysterious and blinded matron of the Nexus who gives them the quest to travel to each region of Boletaria and retrieve the demon's souls to gain power and eventually free the corrupted kingdom of Boletaria from the Old One.
One by one the hero slays the mighty demons that reside in many of Boletaria's notable locations; the Boletarian Palace, Stonefang Tunnel, Tower of Latria, Shrine of Storms and Valley of Defilement. It is also in these places where they encounter the few remaining great men and women of Boletaria. Once the hero claims all the demon's souls and has killed the Arch Demons of each area, the Maiden in Black leads them down below the Nexus to the Old One itself. The Maiden in Black beckons the Old One who invites the hero inside where the now deformed King Allant XII remains. During the final battle Allant claims that because of humanity's own violence and suffering, the Old One is acting mercifully by putting "an end to our tragic realm of existence." Upon Allant's defeat, his last words are a warning to the hero: "You fool. Don't you understand? No one wishes to go on."
During the end game the hero makes one last choice to either slay or walk away from the Maiden in Black. If the hero walks away, they have not succumbed to the temptation of the souls when the fog is lifted and the Maiden departs with the Old One back into the fog into its slumber once again, saving Boletaria and the rest of the world. If, however, the Maiden in Black is killed, they have become lustful for the power of souls, condemning the world with the hero as its ruler at the side of the Old One.