Heroes Chronicles: Warlords of the Wasteland is the first game in the Heroes Chronicles series. Launched on 27 September 2000, simultaneously with three other Chronicles games, Warlords acts as the first chapter of the new saga, telling the story of Tarnum from before he became the Immortal Hero.

As all the Heroes Chronicles games, Warlords is based on the Heroes of Might and Magic III engine, and consists of a campaign, a tutorial, and previews of other three Chronicles games (Heroes Chronicles: Conquest of the Underworld, Heroes Chronicles: Masters of the Elements and Heroes Chronicles: Clash of the Dragons). This totals 12 scenarios. Unlike Heroes III, in Warlords importing extra scenarios or playing in multiplayer is prohibited.

This story takes place before the foundation of the kingdom of Erathia. Once upon a time, the great barbarian King Jarg ruled over those lands. But then the Wizards of Bracaduun came and enslaved the barbarian people. Young Tarnum learns the long-lost history of his people from the last bards and decides to do anything to break the Wizards' rule. Becoming the new Barbarian King, he leads the clans against Bracaduun.

After the death of the woman he fell in love with, Yalla, and the murder of one of the bards by the wizards, Tarnum's noble intentions become a sinister quest for blood and revenge. Decided to destroy the Wizard-Kings at all costs, he enslaves the inhabitants of the Mudlands and orders villages of "traitors" to be burned to the ground, even causing the death of one of his long-lost sisters.

After months of campaign and terrible battles, his advisors express their hope to get back to their home, but Tarnum doesn't listen, obsessed by taking the fortress of Steelhorn. To avoid a rebellion, he has his advisors poisoned, including his old friend Hardac. Accusing the Wizards of his crime, he turns his army into a blood-thirsty Horde. Victory is at hand, but at a terrible cost: Tarnum is now known as the Barbarian Tyrant and has become everything he despised in the Wizards.

Some time later, survivors from Bracaduun flee to the north and found the kingdom of Erathia. During a campaign to conquer the young kingdom, Tarnum is defeated by its first king Rion Gryphonheart. Tarnum soon discovers that Paradise is closed to him. Because of his crimes against his own people, the Ancestors have cursed him to wander the world eternally until he make up for "the tremendous wrongs he performed".