The game takes place right after the events of Overlord, where Gnarl reports evil energy being emitted from the Overlord's conquered domains. Upon his arrival in Mellow Hills, the peasants of Spree surround a large portal, which they believe to be a passage to heaven. Upon arriving however they end up in the "Abyss", an alternate hellish version of their own lands where they are tortured or forced to work. In the Mellow Hills Abyss, the now fallen halfling hero Melvin Underbelly, previously slain by the Overlord in the base game is being punished by becoming even more gluttonous than before, constantly eating to the point of exploding yet returning to the Abyss to restart the same process. Luring him with food, the Overlord uses Melvin's torture as a method of blowing through the Abyss's defences. Melvin ends up rolling into a hole, there unable to eat. The Overlord secures the Abyss Stone, which allows him to take control of the domain.
At this point, Abyss gates appear over the rest of the land. In the Evernight Abyss, Oberon Greenhaze and the remaining elves are being tortured by having to watch a poor-quality re-enactment of their demise at the hands of the dwarves which is used to mock their God, the Mother Goddess, and as an excuse to kill on stage. However, the play constantly begins again from Act 1, since the "terror" prop for Act 3 can not be found. Behind the set, the Overlord finds out the terror is actually the dwarf king Goldo's steam roller, Rollie. With it he finishes the production and burns Oberon to ash with Rollie's flamethrower allowing access to another Abyss Stone.
Back at Heaven's Peak, the women have left through their Abyss gate and dominate the domain where previous Heaven's Peak ruler Sir William the Black is being constantly burnt with the rest of his cult. To appease the women, the Overlord uses Sir William to power humiliating pedal-operated devices for domestic tasks like washing the floor or cutting grass. The women are eventually returned to the normal world, and the Overlord kills Sir William off a second time when he tries to take the next Abyss Stone for himself. In the Golden Abyss, Goldo Golderson has been turned into a large Golden statue, encasing an Abyss Stone. By luring the now demented dwarf forces, they quickly pick away at Goldo until the Abyss Stone is revealed for the Overlord to take.
With all four Abyss Stones, the Overlord gains access to the Infernal Abyss gate in the Ruborian Desert. Despite heavy resistance of its undead forces, the Overlord enters its main Labyrinth. After breaking through a wall constructed with the pieces of a shattered Kahn the Warrior, who still cries out for Jewel, the Overlord confronts the Forgotten God for a final showdown. Apparently the god was trying to gain access to the normal world after having been banished by the Mother Goddess.
Upon his defeat, the Forgotten God tears down his domain and the Abyss gates. While the minions, along with the lost Jester make it back to the normal world safely, the Overlord is stranded in the Abyss. However, the Overlord witnesses the Abyss' forces falling to their knees, as defeating their original master has made the Overlord the new God of the Abyss. Back in the normal world, Gnarl and the minions mourn their loss, and Gnarl admits that he had a soft spot for this particular Overlord and considers the possibility that he might return, ending the scene with the same quote with which he ended Overlord: "Evil will always find a way", at this point revealing that the Overlord's mistress (either Rose or Velvet) is pregnant.