In The Sword of Frost, a direct sequel to Clash of the Dragons, Gelu, wielder of Armageddon's Blade, sets out to destroy the Sword of Frost. Tarnum, having heard of an ancient prophecy that the meeting of the two swords will bring about the end of the world, struggles to stop Gelu. With the recent chaos after the death of Queen Mutare of Nighon, Tarnum is able to take control over the Dungeon creatures of Nighon who are the only ones who wish to fight Gelu, becoming an Overlord. However, ruling these brutal creatures brings out the darkness in Tarnum.
The Sword of Frost is located in the northern lands of the Vori elves. Gelu is half-Vori, so the elves fight against Tarnum. In addition, Tarnum's own troops are prone to internal conflicts. After being shot with a poisoned arrow by a medusa, Tarnum appoints the beholders Neez, Zarm, and Kilkik as his bodyguards and advisors. They take revenge against the medusas, but Zarm dies in the process.
Kija, the third wife of King Kilgor, also chases Gelu for the The Sword of Frost. She plans to steal it from him and give it to her husband so that her son will be named heir to Krewlod. Tarnum cannot convince Kija or Gelu to give up their search, so he decides to gain an edge by adding the Azure Dragons to his army.
In order to learn more about the Sword of Frost, Tarnum captures Gelu's friend and captain, the dwarf Ufretin. While he does so, he replaces his remaining beholder bodyguard Kilkik with the minotaur Trongar and the medusa Zallisa. Tarnum convinces Ufretin to understand him before allowing the dwarf to return to Gelu. Ufretin buys Tarnum enough time to capture Kija and annihilate her army. However, Gelu soon continues his march toward the city of Volee (where the sword is held).
When Tarnum finally beats Gelu to Volee, he discovers that the Sword of Frost has already been taken by Kija, who escaped from her dungeon prison a few weeks earlier. Tarnum prays to the Ancestors, "Please don't let my compassion destroy the world!" Shortly after the events of The Sword of Frost, Gelu fights Kilgor for the Sword of Frost. When the two blades meet in battle, they cause an explosion which destroys the world of Colony. Most of the planet's residents, however, escape through thousands of mysterious portals leading to a new world, Axeoth. This event becomes known as the Reckoning, which leads into Heroes of Might and Magic IV.